Where and when: Room A2 at ENS-Lyon, on Thursday from 1:30pm to 4:30pm

Prerequisites: Nothing strictly required. Basic notions of differential geometry will help.

Objective: The course Effective Methods in Geometry is rather unusual in aiming to show how abstract mathematics can be translated into concrete computations. A wide set of methods will be presented, ranging from combinatorial ones to optimal transport. Many examples will be given: isometric embeddings, word problems and computational topology, optical lenses... A first step in this translation requires to discretize the studied problem that may comes from mathematics itself or from other fields such as physics. We shall see on various examples how to perform this discretization and how to solve the corresponding formulation.

One part will focus on numerical aspects. We shall concentrate on some equations of the Monge-Ampère type that intervene in many fields such as geometry, optimal transport, or optics. We will show how the geometrical discretization of the theory of optimal transport leads to solving optimization problems. In turn, this approach may lead to the realization of concrete objects, such as optical lenses.

1. Theory of optimal transport: Monge problem, Kantorovitch relaxation, Kantorovitch duality, notion of $c$-conjugate, the Wasserstein distance, Mac Cann interpolation.


2. Optimal transport for discrete measures: assignement problems, auction algorithm, entropic regularization.


3. Optimal transport between a measure with density and a discrete measure: connection with computational geometry (Voronoi diagrams, Laguerre diagrams, ...), the Oliker-Prussner algorithm, concave formulation and Newton's methods.


4. Applications to inverse problems in anidolic optics.

Another part will focus on combinatorial aspects issued from topology and geometry, where the underlying mathematical problems have a discrete nature. We will start with the isometric embedding of the flat torus in order to explore PL isometric embeddings as well as other questions mixing topology and geometry.

1. The theorem of Burago and Zalgaller for PL isometric embeddings of polyhedral surfaces.


2. Effective aspects on the existence of topological embedding.


3. What we cannot compute: how the undecidability of the Word problem impacts computational topology.

Course notes:

•  PL isometric embeddings
•  Embedding n-complexes in R2n
•  Deciding linear embeddability

Suggested reading:

• John Stillwell. Classical Topology and Combinatorial Group Theory. Springer, 1995.


• de Longueville, M. A Course in Topological Combinatorics. Springer Universitext, 2013


• Matou\v{s}ek, J. Using the Borsuk-Ulam theorem. Springer Universitext, 2008.


• Jun Kitagawa, Quentin Mérigot, and Boris Thibert, Convergence of a newton algorithm for semi-discrete optimal transport, Journal of European Mathematical Society, 2016, arXiv preprint


• Filippo Santambrogio. Optimal transport for applied mathematicians, Birkäuser, 2015.


• Jocelyn Meyron, Quetin Mérigot, Boris Thibert. Light in Power: A General and Parameter-free Algorithm for Caustic Design, ACM Transactions on Graphics 2018.

Validation: Oral presentation on a research article followed by questions on the part of the course not covered by the article.