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

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 et.al [\emph{8th Symposium on Computational Geometry conf. proc.}, ACM (1992)] 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.

23 pages, 14 figures

References in corpus (1)

• Optimal Transport with Proximal Splitting

Cited by in corpus (6)

• Semi-dual Regularized Optimal Transport
• Differentiation and regularity of semi-discrete optimal transport with respect to the parameters of the discrete measure
• A unifying framework for $n$-dimensional quasi-conformal mappings
• Solving general elliptical mixture models through an approximate Wasserstein manifold
• Minimal convex extensions and finite difference discretization of the quadratic Monge-Kantorovich problem
• Semi-Discrete approximation of Optimal Mass Transport