Volume 49, Number 6, November-December 2015
Special Issue - Optimal Transport
|Page(s)||1693 - 1715|
|Published online||05 November 2015|
A Numerical Algorithm for L2 Semi-Discrete Optimal Transport in 3D
Inria Nancy Grand-Est and LORIA, rue du Jardin Botanique, 54500 Vandoeuvre,
This paper introduces a numerical algorithm to compute the L2 optimal transport map between two measures μ and ν, where μ derives from a density ρ defined as a piecewise linear function (supported by a tetrahedral mesh), and where ν 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 μ. The numerical algorithm is experimented and evaluated on several datasets, with up to hundred thousands tetrahedra and one million Dirac masses.
Mathematics Subject Classification: 49M15 / 35J96 / 65D18
Key words: Optimal transport / power diagrams / quantization noise power / Lloyd relaxation
© EDP Sciences, SMAI 2015
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.