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

Lévy, Bruno

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

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.

Classification : 49M15, 35J96, 65D18
Mots clés : Optimal transport, power diagrams, quantization noise power, Lloyd relaxation

L. Ambrosio and N. Gigli, A users guide to optimal transport, Modelling and Optimisation of Flows on Networks. Lect. Notes Math. (2013) 1–155. | MR

N. Amenta, S. Choi and G. Rote, Incremental constructions con brio, in Proc. of the Nineteenth Annual Symposium on Computational Geometry, SCG’03, New York, NY, USA. ACM (2003) 211–219.

F. Aurenhammer, Power diagrams: Properties, algorithms and applications. SIAM J. Comput. 16 (1987) 78–96. | DOI | MR | Zbl

F. Aurenhammer, F. Hoffmann and B. Aronov, Minkowski-type theorems and least-squares partitioning, in Proc. of Symposium on Computational Geometry (1992) 350–357.

J.-D. Benamou and Y. Brenier, A computational fluid mechanics solution to the monge-kantorovich mass transfer problem. Numer. Math. 84 (2000) 375–393. | DOI | MR | Zbl

J.-D. Benamou, G. Carlier, Q. Mérigot and E. Oudet, Discretization of functionals involving the monge-ampère operator. Preprint arXiv:1408.4536 (2014). | MR

N. Bonneel, M. Van De Panne, S. Paris and W. Heidrich, Displacement interpolation using lagrangian mass transport. ACM Trans. Graph. 30 (2011) 158. | DOI

Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions. Commun. Pure Appl. Math. 44 (1991) 375–417. | DOI | MR | Zbl

R. Burkard, M. Dell’Amico and S. Martello, Assignment Problems. SIAM (2009). | MR | Zbl

L. Caffarelli, The Monge-Ampère Equation and Optimal Transportation, an Elementary Review. Optimal Transportation and Applications (Martina Franca, 2001). Lect. Notes Math. (2003) 1–10. | MR

G. De Philippis and A. Figalli, Partial Regularity for Optimal Transport Maps. Publications mathématiques de l’IHES (2014) 1–32.

C. Delage and O. Devillers, Spatial sorting, in CGAL User and Reference Manual. CGAL Editorial Board 3.9 edition (2011).

Q. Du, V. Faber and M. Gunzburger, Centroidal voronoi tessellations: Applications and algorithms. SIAM Rev. 41 (1999) 637–676. | DOI | MR | Zbl

Q. Du, V. Faber and M. Gunzburger, Centroidal Voronoi tessellations: applications and algorithms. SIAM Rev. 41 (1999) 637–676. | DOI | MR | Zbl

H. Edelsbrunner and E. P. Mücke, Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. Acm Trans. Graph 9 (1990) 66–104. | DOI | Zbl

X. Gu, F. Luo, J. Sun and S.-T. Yau, Variational principles for minkowski type problems, discrete optimal transport, and discrete Monge-Ampère equations. Preprint arXiv:1302.5472 (2013). | MR

M. Iri, K. Murota and T. Ohya, A fast Voronoi-diagram algorithm with applications to geographical optimization problems, in Proc. of the IFIP (1984) 273–288. | MR | Zbl

R. Jordan, D. Kinderlehrer and F. Otto, The variational formulation of the fokker-planck equation. SIAM J. Math. Anal. 29 (1999) 1–17. | DOI | MR | Zbl

B. Lévy, Restricted voronoi diagrams for (re)-meshing surfaces and volumes, in Curves and Surfaces conference proceedings (2014).

B. Lévy and Y. Liu, Lp Centroidal Voronoi Tesselation and its Applications. SIGGRAPH conference proceedings ACM Trans. Graph. (2010).

D.C. Liu and J. Nocedal, On the limited memory bfgs method for large scale optimization. Math. Program. 45 (1989) 503–528. | DOI | MR | Zbl

Y. Liu, HLBFGS, a hybrid l-bfgs optimization framework which unifies l-bfgs method, preconditioned l-bfgs method, preconditioned conjugate gradient method. http://research.microsoft.com/en-us/um/people/yangliu/software/HLBFGS/.

Y. Liu, W. Wang, B. Lévy, F. Sun, D.-M. Yan, L. Lu and C. Yang, On centroidal Voronoi tessellation-energy smoothness and fast computation. ACM Trans. Graph. 28 (2009) 1–17. | DOI

S.P. Lloyd, Least squares quantization in pcm, IEEE Trans. Inform. Theory 28 (1982) 129–137. | DOI | MR | Zbl

R.J. Mccann, Existence and uniqueness of monotone measure-preserving maps. Duke Math. J. 80 (1995) 309–323. | DOI | MR | Zbl

F. Mémoli, Gromov-wasserstein distances and the metric approach to object matching. Found. Comput. Math. 11 (2011) 417–487. | DOI | MR | Zbl

Q. Mérigot, A multiscale approach to optimal transport. Comput. Graph. Forum 30 (2011) 1583–1592. | DOI

A. Meyer and S. Pion, FPG: A code generator for fast and certified geometric predicates, in Proc. of Real Numbers and Computers, Santiago de Compostela, Espagne (2008) 47–60.

P. Milgrom and I. Segal, Envelope Theorems for Arbitrary Choice Sets. Econometrica 70 (2002) 583–601. | DOI | MR | Zbl

G. Monge, Mémoire sur la théorie des déblais et des remblais. Histoire de l’Acadmie Royale des Sciences (1781), (1784) 666–704.

J. Munkres, Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5 (1957) 32–38. | DOI | MR | Zbl

V. Nivoliers, Echantillonage pour l’approximation de fonctions sur des maillages. Ph.D. thesis, IAEM, Université de Lorraine (2012).

V. Nivoliers and B. Lévy, Approximating functions on a mesh with restricted voronoi diagrams, in ACM/EG Symposium on Geometry Processing/Computer Graphics Forum (2013).

N. Papadakis, G. Peyré and E. Oudet, Optimal transport with proximal splitting. SIAM J. Imag. Sci. 7 (2014) 212–238. | DOI | MR | Zbl

F. Santambrogio, Introduction to Optimal Transport Theory, in Optimal Transport, Theory and Applications. London Math. Soc. Lect. Notes Ser. (2014) 3–21. | MR

J.R. Shewchuk, Robust Adaptive Floating-Point Geometric Predicates, in Symposium on Computational Geometry (1996) 141–150.

C. Villani, Optimal transport: Old and New. Grundlehren der mathematischen Wissenschaften. Springer, Berlin (2009). | MR | Zbl

D. Yan, W. Wang, B. Lévy and Y. Liu, Efficient computation of clipped voronoi diagram for mesh generation. Computer-Aided Design Journal 45 (2013) 843–852. | DOI | MR