2017/06/23 by Valentin Hartmann, Hartmann, Valentin, Dominic Schuhmacher +1 · 1 citation
Computer Science · Mathematics · #51N20 #62-09 (Secondary) #65D18 (Primary) #Complexity and Algorithms in Graphs #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Numerical Analysis (math.NA) #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.1706.07650
openalex publication_date 2017/06/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We consider the problem of finding an optimal transport plan between an absolutely continuous measure μ on X ⊂ ℝd and a finitely supported measure ν on ℝ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.