A numerical algorithm for L2 semi-discrete optimal transport in 3D

Bruno Lévy 1
1 ALICE - Geometry and Lighting
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : 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.
Type de document :
Article dans une revue
ESAIM: Mathematical Modelling and Numerical Analysis, EDP Sciences, 2015, 49 (6), pp.1693 - 1715. 〈10.1051/m2an/2015055〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01105021
Contributeur : Nicolas Ray <>
Soumis le : lundi 19 janvier 2015 - 16:00:24
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23

Lien texte intégral

Identifiants

Collections

Citation

Bruno Lévy. A numerical algorithm for L2 semi-discrete optimal transport in 3D. ESAIM: Mathematical Modelling and Numerical Analysis, EDP Sciences, 2015, 49 (6), pp.1693 - 1715. 〈10.1051/m2an/2015055〉. 〈hal-01105021〉

Partager

Métriques

Consultations de la notice

238