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

arXiv1706.07403MaRDI QIDQ6288191FDOQ6288191

Authors: Valentin Hartmann 

Publication date: 22 June 2017

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 $mu$ on $mathbb{R}^d$ to a discrete measure $u$ 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.

This page was built for publication: A Geometry-Based Approach for Solving the Transportation Problem with Euclidean Cost

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6288191)