Fix $n>1$ distinguished points $x_1,\ldots, x_n\in \mathbb R^d$, the Voronoi tessellations are the subsets $V_1,\ldots V_n\subset\mathbb R^d$ defined by

$$V_k~~ := ~~ \big\{x\in\mathbb R^d:\quad |x-x_k|^2~\le ~ |x-x_i|^2,~ \mbox{ for all } i=1,\ldots, n\big\}.$$

Next we introduce $n$ translation parameters $c_1,\ldots, c_n\in (-\infty,\infty)$, then the Laguerre tessellations are given by, with $C:=(c_1,\ldots, c_n)\in\mathbb R^n$,

$$L_k(C)~~ := ~~ \big\{x\in\mathbb R^d:\quad |x-x_k|^2-c_k~\le ~ |x-x_i|^2-c_i,~ \mbox{ for all } i=1,\ldots, n\big\}.$$

Assume we are given a smooth density function $\rho:\mathbb R^d\to\mathbb R_+$, and discrete probability weights $\alpha_1,\ldots,\alpha_n\subset (0,1)$ satisfying $\sum_{i=1}^k\alpha_i=1$, my question is how to find $C\in\mathbb R^n$ s.t.

$$\int_{L_i(C)}\rho(x)dx=\alpha_i,~ \mbox{ for all } i=1,\ldots, n.$$

The problem arises in my research, and I am interested in the computation of $\nabla_{x_i}c_k$. I have tried with some particular cases, i.e. $d=1$ or $n=2$, where some concrete analysis can be carried out. But for general $d$ and $n$, I have no idea whether there is some related literature. Any solution or reference will highly appreciated!


The following two articles might be helpful:

Aurenhammer, F.; Hoffmann, F.; Aronov, B., Minkowski-type theorems and least-squares clustering, Algorithmica 20, No. 1, 61-76 (1998). ZBL0895.68135.

Gu, Xianfeng; Luo, Feng; Sun, Jian; Yau, Shing-Tung, Variational principles for Minkowski type problems, discrete optimal transport, and discrete Monge-Ampère equations, Asian J. Math. 20, No. 2, 383-398 (2016). ZBL1339.49039.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.