Some algorithmic aspects of semi-discrete optimal transport.

In semi-discrete optimal transport, a measure with a density is transported to a sum of Dirac masses. This setting is very well adapted to a computer implementation, because the transport map is determined by a vector of parameters (associated with each Dirac mass) that maximizes a convex function (Kantorovich dual). An efficient numerical solution mechanism requires to carefully orchestrate the interplay of geometry and numerics. On geometry, I will present two algorithms to efficiently compute Laguerre cells, one that uses arbitrary precision predicates, and one that uses standard double-precision arithmetics. On numerical aspects, when implementing a Newton solver (a 3D version of [Kitagawa Merigot Thibert]), the main difficulty is to assemble the Hessian of the objective function, a sparse matrix with a non-zero pattern that changes during the iterations. By exploiting the relation between the Hessian and the 1-skeleton of the Laguerre diagram, it is possible to efficiently construct the Hessian. The algorithm can be used to simulate incompressible Euler fluids [Merigot Gallouet]. I will also show applications of these algorithms in more general settings (transport between surfaces and approximation of general Laguerre diagrams).Non UBCUnreviewedAuthor affiliation: Inria LorainneOthe