Semi-discrete optimal transport - the case p=1
For researchers in optimal transport and computational geometry, this work extends algorithmic solutions from the well-studied squared Euclidean case to the Euclidean distance, enabling new applications in resource allocation and statistical testing.
The paper addresses the semi-discrete optimal transport problem with Euclidean distance cost (p=1), presenting an algorithm analogous to the squared Euclidean case. It demonstrates the algorithm's performance on test cases and introduces goodness-of-fit partitions as a visual tool for assessing sample consistency with a density.
We consider the problem of finding an optimal transport plan between an absolutely continuous measure $μ$ on $\mathcal{X} \subset \mathbb{R}^d$ and a finitely supported measure $ν$ on $\mathbb{R}^d$ when the transport cost is the Euclidean distance. We may think of this problem as closest distance allocation of some ressource continuously distributed over space to a finite number of processing sites with capacity constraints. This article gives a detailed discussion of the problem, including a comparison with the much better studied case of squared Euclidean cost ("the case $p=2$"). We present an algorithm for computing the optimal transport plan, which is similar to the approach for $p=2$ by Aurenhammer, Hoffmann and Aronov [Algorithmica 20, 61-76, 1998] and Mérigot [Computer Graphics Forum 30, 1583--1592, 2011]. We show the necessary results to make the approach work for the Euclidean cost, evaluate its performance on a set of test cases, and give a number of applications. The later include goodness-of-fit partitions, a novel visual tool for assessing whether a finite sample is consistent with a posited probability density.