The defenseIt will take place on Thursday 20th october at 1:30 PM in the C5 room of the Nautibus building, Villeurbanne.

Title

Symmetric semi-discrete optimal transport for mesh interpolation

Abstract

This thesis aims to develop geometric methods to approximate displacement interpolation, derived from optimal transport. Optimal transport is a mathematical theory modeling movements of matter under a cost minimization constraint, with many applications in physics, computer graphics and geometry. The minimum displacement cost between two distributions defines a distance, which itself is at the origin of displacement interpolation. This interpolation may under certain conditions present discontinuities, that the discretized approximations of the optimal transport do not always successfully capture. The work of this thesis aims to develop an approximation that captures these discontinuities well. Our method relies on semi-discrete optimal transport, where only one of the distributions is discretized, thus accurately capturing the discontinuities of the distribution that remains continuous. The transport plans thus obtained partition the continuous distribution into cells associated with the samples of the discretization. A semi-discrete optimal transport plan can thus be assimilated to a power diagram made up of these cells. This variant of optimal transport however has the disadvantage of breaking the symmetry between the two distributions. We start by formalizing our problem as the search for a pair of transport plans coupled through the barycenters of their cells. We then present an algorithm for calculating these coupled transport plans. This first algorithm is based on a classical alternating algorithm scheme, successively computing the transport plans and the barycenters of their cells until convergence. The results obtained from this algorithm allow to interpolate between the initial distributions while maintaining a satisfactory precision, in particular when it comes to discontinuities, including when the discretization of the distributions is done with relatively few points. We then present our exploration of optimization methods for solving the same problem. These methods express the constraints of our problem as a critical point of a functional, and aim to reach these points using algorithms such as Newton’s method. However, this approach did not yield conclusive results, as the functions involved were too noisy to lend themselves well to optimization algorithms.

Keywords: Optimal transport, Interpolation, Optimization, Algorithmic geometry

Jury

• • Julie Delon (reviewer), Université Paris Cité
  • Boris Thibert (reviewer), Université Grenoble Alpes
  • Dominique Attali (examiner), CNRS/Université Grenoble Alpes
  • Filippo Santambrogio (examiner), Université Lyon 1
  • Nicolas Bonneel (advisor), CNRS/Université Lyon 1
  • Julie Digne (co-advisor), CNRS/Université Lyon 1
  • Bruno Lévy (co-advisor), Inria Nancy Grand Est