A Geometry-Based Approach for Solving the Transportation Problem with Euclidean Cost

2017/06/22 by Valentin N. Hartmann, Hartmann, Valentin, Valentin Hartmann
Business, Management and Accounting · Mathematics · Social Sciences · #FOS: Mathematics #Facility Location and Emergency Management #Numerical Analysis (math.NA) #Point processes and geometric inequalities #Transportation Planning and Optimization

paper · pdf · doi:10.48550/arxiv.1706.07403

openalex publication_date 2017/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 ℝ^d to a discrete measure ν that is supported on a finite set in ℝ^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 ℝ^d. From the proof an algorithm is derived to compute this partition.

Related

• The geometry of optimal transportation
• Semi-discrete optimal transport - the case p=1
• Optimal transportation for a quadratic cost with convex constraints and applications
• Regularity for the optimal transportation problem with Euclidean distance squared cost on the embedded sphere
• Conditions for existence of single valued optimal transport maps on convex boundaries with nontwisted cost