Semi-discrete optimal transport - the case p=1

Abstract

The Monge-Kantorovich problem of finding a minimum cost coupling between an absolutely continuous measure \(\mu\) on \(\mathcal{X} \subset \mathbb{R}^d\) and a finitely supported measure \(\nu\) on \(\mathbb{R}^d\) is considered for the special case of the Euclidean cost function. This corresponds to the natural problem of closest distance allocation of some ressource that is continuously distributed in space to a finite number of processors with capacity constraints. A systematic discussion of the choice of Euclidean cost versus squared Euclidean cost is provided from the practitioner's point of view. We then show that the above problem has a unique solution that can be either described by a transport map \(T \colon \mathcal{X} \to \mathbb{R}^d\) or by a partition of \(\mathcal{X}\). We provide an algorithm for computing this optimal transport partition, adapting the approach by Aurenhammer, Hoffmann and Aronov (1998) and M\'erigot~(2011) to the Euclidean cost. We give two types of numerical applications to demonstrate the use of the algorithm and to illustrate aspects of the semi-discrete problem and the choice of the Euclidean cost.