Let $\mu(dx)=\sum_{i=1}^np_i\delta_{x_i}(dx)$ and $\nu(dy)=\rho(y)dy$ be two probability measures on $\mathbb R^d$, where $\nu$ has a bounded support. Consider the $2-$Wasserstein distance below:

$$W_2(\mu,\nu)^2 \quad := \quad \inf_{\pi\in\Pi(\mu,\nu)}~ \int_{\mathbb R^d\times\mathbb R^d}~ |x-y|^2\pi(dx,dy),$$

where $\Pi(\mu,\nu)$ denotes the collection of couplings $\pi$ of $\mu$ and $\nu$. Let $\pi^*$ be its optimiser, then there exists $(V_i)_{1\le I\le n}$ of $\mathbb R^d$ such that

$$\cup_{i=1}^nV_i~=~\mathbb R^d,\quad \nu[V_i\cap V_j]~=~0,~ \forall i\neq j,\quad \pi^*(dx,dy)~=~\nu(dy)\otimes K_y(dx),$$


$$K_y(dx) \quad:=\quad \sum_{i=1}^n {\bf 1_{y\in V_i}}\delta_{x_i}(dx).$$

Roughly speaking, every $V_i$ is transported to $x_i$ under the optimiser $\pi^*$. My question is, for given the $p_i>0$ and $\rho$ (which can be assumed to be as good as possible), under which condition on $x_1,\ldots, x_n$, each $x_i$ is the barycentre of $V_i$??

To illustrate this, let us look at an example. Take $d=2$, $n=10$ and $\nu$ be a uniform distribution on the square, then the optimiser $\pi^*$ is given as follows:

enter image description here

Here the green points are the given $x_i$, the regions stand for $V_i$ and the red points for the barycentres of $V_i$.

  • $\begingroup$ Could you specify a bit more what you are hoping for? Really a condition just on $x_i$ and independent of $p_i$ and $\nu$? $\endgroup$
    – Steve
    Jun 16, 2018 at 12:29
  • $\begingroup$ @Steve Thanks for the reply. All $p_i$ are strictly positive, and the density $\rho$ could be assumed to be smooth enough or even have a bounded support. $\endgroup$
    – user111097
    Jun 17, 2018 at 9:54
  • $\begingroup$ Ok thanks. To understand the problem a bit better, could you give a source for the simplified form of the optimizer you are using? Do you perhaps know if the $V_i$ are convex under some conditions? $\endgroup$
    – Steve
    Jun 18, 2018 at 20:06
  • $\begingroup$ @Steve Yes. $V_i$ are all convex polygons $\endgroup$
    – user111097
    Jun 18, 2018 at 21:01

1 Answer 1


You ask "given the $p_i>0$ and $\rho$ (which can be assumed to be as good as possible), under which condition on $x_1,\ldots, x_n$ each $x_i$ is the barycentre of $V_i$??"

In one sense the question answers itself: ``the required condition is exactly that $x_i$ equals the barycentre of $V_i$".

But more interesting than the answer is the question itself, and the empirical means of replacing modifying $x_1,x_2, \ldots$ with $x'_1=barycenter(V_1)$, $ x_2'=barycenter(V_2)$, etc. Repeating this process apparently gives you the desired Voronoi cellulation, where this idea first appears in Lloyd's Algorithm.

The Wikipedia page is useful (https://en.wikipedia.org/wiki/Lloyd%27s_algorithm), and the article https://ieeexplore.ieee.org/document/1057168 appears to be interesting.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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