A Geometry-Based Approach for Solving the Transportation Problem with Euclidean Cost
Provides a theoretical foundation and computational method for optimal transport between continuous and discrete measures, relevant to fields like image processing and economics.
The paper addresses the semi-discrete Monge problem with Euclidean cost, proving existence and uniqueness of an optimal transport map via an explicit construction linking it to additively weighted Voronoi partitions, and derives an algorithm to compute this partition.
In the semi-discrete version of Monge's problem one tries to find a transport map $T$ with minimum cost from an absolutely continuous measure $μ$ on $\mathbb{R}^d$ to a discrete measure $ν$ that is supported on a finite set in $\mathbb{R}^d$. The problem is considered for the case of the Euclidean cost function. Existence and uniqueness is shown by an explicit construction which yields a one-to-one mapping between the optimal $T$ and an additively weighted Voronoi partition of $\mathbb{R}^d$. From the proof an algorithm is derived to compute this partition.