A Numerical Algorithm for $L_2$ Semi-Discrete Optimal Transport in 3D

Lévy, Bruno¹ 

¹ Inria Nancy Grand-Est and LORIA, rue du Jardin Botanique, 54500 Vandoeuvre, France.

ESAIM: Mathematical Modelling and Numerical Analysis , Optimal Transport, Tome 49 (2015) no. 6, pp. 1693-1715

Résumé

This paper introduces a numerical algorithm to compute the $L_2$ optimal transport map between two measures $\mu$ and $\nu$, where $\mu$ derives from a density $\rho$ defined as a piecewise linear function (supported by a tetrahedral mesh), and where $\nu$ is a sum of Dirac masses. I first give an elementary presentation of some known results on optimal transport and then observe a relation with another problem (optimal sampling). This relation gives simple arguments to study the objective functions that characterize both problems. I then propose a practical algorithm to compute the optimal transport map between a piecewise linear density and a sum of Dirac masses in 3D. In this semi-discrete setting [Aurenhammer et al., Proc. of 8th Symposium on Computational Geometry (1992) 350–357] showed that the optimal transport map is determined by the weights of a power diagram. The optimal weights are computed by minimizing a convex objective function with a quasi-Newton method. To evaluate the value and gradient of this objective function, I propose an efficient and robust algorithm, that computes at each iteration the intersection between a power diagram and the tetrahedral mesh that defines the measure $\mu$. The numerical algorithm is experimented and evaluated on several datasets, with up to hundred thousands tetrahedra and one million Dirac masses.

Détail

Reçu le : 2015-07-15
DOI : 10.1051/m2an/2015055

Classification : 49M15, 35J96, 65D18
Keywords: Optimal transport, power diagrams, quantization noise power, Lloyd relaxation