# Semi-discrete Wasserstein distance to uniform

Does the $$p$$-Wasserstein distance have a simpler expression when applied to these two distributions :

• A uniform distribution on $$[0,1]^d$$
• A discrete distribution with $$N$$ equally-weighted point mass all in $$[0,1]^d$$

I'm trying to compute a closed form expression to this particular setting for the $$p$$-Wasserstein distance, but i'm having some trouble. If it makes things simpler, you can take $$p=2$$.

In a more intuitive point of view, the question is to calculate the minimal transport cost of a point to a uniform distribution around it.

Finaly, if you have some references in mind on semi-discrete Wasserstein distances, it could help me :)

## 1 Answer

$$\newcommand{\R}{\mathbb{R}}$$ Welcome to MathOverflow! My conjecture is as follows. Let $$a_1,\dots,a_N$$ be the distinct points in question. For $$i\in[N]:=\{1,\dots,N\}$$ and each $$k=(k_1,\dots,k_N)\in\R^N$$, let $$$$X_i(k):=\{x\in[0,1]^d\colon|x-a_i|^p-|x-a_j|^p\le k_i-k_j\ \ \forall j\in[N]\setminus\{i\}\}. \tag{1}$$$$ Note that, if $$k_i=0$$ for all $$i$$, then the family $$X(k):=(X_i(k))_{i\in[N]}$$ is the Voronoi tesselation for the points $$a_1,\dots,a_N$$. So, one may refer to $$X(k)$$ in general as the $$k$$-Voronoi tesselation.

Conjecture 1 For some $$k\in\R^N$$, the cells $$X_i(k)$$ of the $$k$$-Voronoi tesselation $$X(k)$$ are all of the same $$d$$-volume, $$1/N$$.

Let us denote such a vector $$k$$ by $$k_*$$.

Conjecture 2 The optimal transportation of the uniform distribution on the set $$\{a_1,\dots,a_N\}$$ to the uniform distribution on the $$d$$-cube $$[0,1]^d$$ is given by the transportation of the $$\frac1N$$-mass at each point $$a_i$$ to $$\frac1N\,\times\big(\text{the uniform distribution on the cell }X_i(k_*)\big)$$.

So, the $$p$$th power of the $$p$$-Wasserstein distance will be $$\sum_{i=1}^N\int_{X_i(k_*)}|x-a_i|^p\,dx.$$

Informal justification: Let $$m_i(A)$$ denote the mass transported from a point $$a_i$$ to a Borel set $$A\subseteq[0,1]^d$$. We have to minimize $$\begin{equation*} \sum_i\int_{[0,1]^d}|x-a_i|^p m_i(dx) \end{equation*}$$ given that $$m_i\ge0$$, $$\int_{[0,1]^d}m_i(dx)=1$$ for all $$i$$, and $$\sum_i m_i(dx)=dx$$. Varying the measures $$m_i$$ and using Lagrange multipliers, we have $$|x-a_i|^p=k_i+\mu(x)$$ for some $$k=(k_1,\dots,k_N)\in\R^N$$, some function $$\mu$$, all $$x$$, and all $$i$$ such that $$x$$ is in the support set (say $$S_i$$) of the measure $$m_i$$. It follows that $$|x-a_i|^p-|x-a_j|^p=k_i-k_j$$ for all $$x$$ and all $$i,j$$ such that $$x\in S_i\cap S_j$$. This gives rise to formula (1).