# On semi-discrete Wasserstein distance

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),$$

where

$$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:

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$.

• 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$? Jun 16, 2018 at 12:29
• @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. Jun 17, 2018 at 9:54
• 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? Jun 18, 2018 at 20:06
• @Steve Yes. $V_i$ are all convex polygons Jun 18, 2018 at 21:01

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.