On semi-discrete Wasserstein distance

Question

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

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.