Publications by year

2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  

Most documents on this website are protected by copyright. By clicking on a PDF icon, you confirm that you or your institution has the right to do so. Note that the definitive versions of all EG papers (Eurographics,...) can be downloaded from ACM papers (Siggraph, ...) can be downloaded from


“A Numerical Algorithm for L2 semi-discrete optimal transport in 3D”
Bruno Lévy
ESAIM M2AN (Mathematical Modeling and Numerical Analysis), 2015

Abstract: 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 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. Merigot proposed a hierarchical algorithm that improves the speed of convergence, together with an implementation in 2D. To evaluate the value and gradient of the objective function for the 3D problem, 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.

BibTex reference

   TITLE      = "A Numerical Algorithm for L2 semi-discrete optimal transport in 3D",
   AUTHOR     = "Bruno Lévy",
   JOURNAL    = "ESAIM M2AN (Mathematical Modeling and Numerical Analysis)",
   YEAR       = "2015",

Supplemental material, links, hindsight ...