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!


1 Answer 1


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