Séminaire de Géométrie Algorithmique et Combinatoire

Le Séminaire de Géométrie Algorithmique et Combinatoire vise à regrouper des exposés dans ce domaine au sens le plus large, et dans les disciplines connexes en mathématiques et informatique. Il est ouvert à tous les chercheurs et étudiants intéressés. Les exposés sont destinés à un public large.

Il se tient un jeudi par mois, de 14h à 17h, à l'Institut Henri Poincaré à Paris (plan d'accès), en salle 201.

Contact: seminaire gac ens fr. Pour recevoir les annonces de ce séminaire, envoyer un message à cette adresse avec [inscription] dans le titre.

La liste des exposés passés est disponible ici.

13 oct. 2016
14h Gabriel Peyré CNRS et DMA, École normale supérieure, Paris
From Monge-Kantorovich to Gromov-Wasserstein : Optimal Transport and Barycenters Between Several Metric Spaces
Optimal transport (OT) has become a fundamental mathematical theoretical tool at the interface between calculus of variations, partial differential equations and probability. It took however much more time for this notion to become mainstream in numerical applications. This situation is in large part due to the high computational cost of the underlying optimization problems. There is however a recent wave of activity on the use of OT-related methods in fields as diverse as computer vision, computer graphics, statistical inference, machine learning and image processing. In this talk, I will review an emerging class of numerical approaches for the approximate resolution of OT-based optimization problems. These methods make use of an entropic regularization of the functionals to be minimized, in order to unleash the power of optimization algorithms based on Bregman-divergences geometry. This results in fast, simple and highly parallelizable algorithms, in sharp contrast with traditional solvers based on the geometry of linear programming. For instance, they allow for the first time to compute barycenters (according to OT distances) of probability distributions discretized on computational 2-D and 3-D grids with millions of points. This offers a new perspective for the application of OT in machine learning (to perform clustering or classification of bag-of-features data representations) and imaging sciences (to perform color transfer or shape and texture morphing). These algorithms also enable the computation of gradient flows for the OT metric, and can thus for instance be applied to simulate crowd motions with congestion constraints. This is a joint work with M. Cuturi and J. Solomon.
15h30 Frédéric Chazal INRIA Saclay—Île-de-France
Subsampling methods for persistent homology
Computational topology has recently seen an important development toward data analysis, giving birth to Topological Data Analysis. Persistent homology appears as a fundamental tool in this field. It is usually computed from filtrations built on top of data sets sampled from some unknown (metric) space, providing "topological signatures" revealing the structure of the underlying space. When the size of the sample is large, direct computation of persistent homology often suffers two issues. First, it becomes prohibitive due to the combinatorial size of the considered filtrations and, second, it appears to be very sensitive to noise and outliers. In this talk we will present a method to overcome these issues by computing persistent diagrams from several subsamples and combining them in order to efficiently infer robust and relevant topological information from data.
10 nov. 2016
14h David Coeurjolly CNRS et LIRIS, Université de Lyon
Geometry Procesing on Digital Surfaces
Digital Geometry can be simply characterised as a set of definitions, theorems and algorithmic tools that deal with the geometric properties of objects defined on regular lattices. Originating from shape processing in 2D and volumetric images, this specific constraint on the input data implies new axioms and results with strong connections between various fields such as computational geometry, discrete mathematics (arithmetic, theory of words) and image processing. In this presentation, I first introduce the specificities of the model and then present several geometry processing tools we have developed dedicated to digital surfaces.
15h30 Jean-Marie Mirebeau CNRS et Université Paris-Sud
Calcul de chemins minimaux avec pénalisation de courbure, via l'algorithme du Fast Marching
Motivés par des applications en planification de mouvement et en segmentation d'image, nous considérons des modèles de plus courts chemins avec pénalisation de courbure, tels que les élasticas d'Euler/Mumford, ou la voiture de Reed-Shepp avec ou sans marche arrière. Notre stratégie numérique, pour le calcul du chemin d'énérgie minimale joignant deux points donnés, est d'approcher ces modèles singuliers à l'aide de métriques Riemanniennes ou Finsleriennes fortement anisotropes sur l'espace produit $\RR^d\times\SS^{d-1}$. Les équations eikonales associées sont ensuites résolues via des variantes spécialisées de l'algorithme du Fast-Marching.
8 déc. 2016
Gil Kalai Hebrew University of Jerusalem
Xavier Goaoc Université Paris-Est Marne-la-Vallée
19 janv. 2017
14h
15h30
23 févr. 2017
14h
15h30
23 mars 2017
14h
15h30
20 avr. 2017
14h
15h30
11 mai 2017
14h
15h30
22 juin 2017
14h
15h30

Le séminaire bénéficie du soutien de l'Institut Henri Poincaré.

Le comité scientifique est constitué de:

• Éric Colin de Verdière (CNRS, LIGM, U. Paris-Est Marne-la-Vallée),
• Xavier Goaoc (LIGM, U. Paris-Est Marne-la-Vallée),
• Nabil Mustafa (LIGM, U. Paris-Est Marne-la-Vallée, ESIEE),
• Steve Oudot (Geometrica, Inria Saclay),
• Vincent Pilaud (CNRS, LIX, École Polytechnique),
• Michel Pocchiola (IMJ-PRG, Université Pierre et Marie Curie).

Le comité d'organisation est constitué d'Éric Colin de Verdière, Steve Oudot et Vincent Pilaud.