Consider the uniform distribution $\lambda$ on $[0,1]$, and a point measure $\rho$ with density $\frac{1}{2} (\delta\_{x\_1} + \delta\_{x\_2})$, where we have $0\le x\_1 \le x\_2 < 1/2$.


If our cost is just the distance $c(x,y) = | x - y|$, it seems reasonably clear that the optimal transport map from $\lambda$ to $\rho$ would be 
$$
T(x) = \begin{cases}
x\_1 & \text{if } x < 1/2\\
x\_2 & \text{if } x \ge 1/2 
\end{cases}
$$
and the optimal coupling would have density along the lines of 
$$
\mathrm{d}\pi(x,y) = \frac{1}{2} \left( \chi\_{[0,1/2)}(x) \delta\_{x\_1}(y) + \chi\_{[1/2,1]}(x) \delta\_{x\_2}(y)\right),
$$
where $\chi\_{A}$ is an indicator function. However, consider the usual Kantorovich dual formulation where we want to find 
$$
\sup\_{\phi, \psi} 
\left( \int\_0^1 \phi(y) \, \mathrm{d}y - \frac{1}{2}(\psi\_1 + \psi\_2)\right)
=
\sup\_{\psi} 
\left( \int\_0^1 \psi^c(y) \, \mathrm{d}y - \frac{1}{2}(\psi\_1 + \psi\_2)\right)
$$
where the supremum is taken over all 1-Lipschitz functions $\phi$ and $\psi = \{ \psi\_1,\psi\_2\}$ such that $| \psi\_1 - \psi\_2 | \le | x\_1 - x\_2 |$, and where $\phi(y) - \psi\_i \le |x\_i - y|$.
Furthermore $\psi^c$ is the usual $c$-transform, which in this case is
$$
\psi^c(y) = \min\_{i} \left(\psi\_i + | x\_i - y |\right).
$$
(There is some abuse of notation here BTW)


**My problem is:** This dual solution doesn't seem to work in this case. Ideally we want Laguerre cells 
$$
\mathrm{Lag}\_1 := \{ x : |x - x\_1| + \psi\_1 \le |x - x\_2| + \psi\_2, \,\, \forall j \neq i\} = [0,1/2),
$$
and similarly $\mathrm{Lag}\_2 = [1/2,1]$. **I just can't see how we can find values $\psi\_1, \psi\_2$ that give us these Laguerre cells**. If say $\psi\_2 = \psi\_1 + \varepsilon$ where $\varepsilon < x\_2 - x\_1$, then $\psi$ would be "$c$-convex" and we would get
$$
\mathrm{Lag}\_1 = [0, (x\_2 - x\_1 + \varepsilon)/2)
$$
which obviously has measure of less than $1/2$. If $\varepsilon > x\_2 - x\_1$ then we'd have that $\mathrm{Lag}\_1 = [0,1]$ and $\mathrm{Lag}\_2 = \emptyset$, and furthermore it seems that $\psi$ would not be $c$-convex any more.


Am I missing something here? I can't see in the theory (e.g. Theorem 5.10 from Villani's *Optimal Transport: Old and New*) why we wouldn't be able to have a dual form in this example. Also in the question **[On semi-discrete Wasserstein distance](https://mathoverflow.net/questions/302852/on-semi-discrete-wasserstein-distance)** there is a similar issue: you can see that the green points are not contained within their respective Laguerre cells, which may mean it is similarly impossible to find a $c$-convex $\psi$.



A problem with the dual form of semi-discrete optimal transport
Just like to share for anyone who ends up here - my problem was a lack of strict convexity in the cost function when represented as $c(x,y) = h(x-y)$. The function $h(x-y) = |x - y|$ is not strictly convex, so according to theory that can be found, for example in [Gangbo and McCann](https://projecteuclid.org/euclid.acta/1485890981), there is no guarantee of a *unique* transport solution and dual solution for which the usual $c$-transform relationship holds. Also, Vilanni's text proves existence and I missed the fact that there are no guarantees of uniqueness.


