Séminaire Francilien 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.

On reprend les activités en presentiel un jeudi par mois à 14h, à l'IHP, en salle 01.

Pour recevoir les annonces de ce séminaire, envoyer un message à arnau [dot-sign] padrol [the-funny-at-sign] imj-prg [dot-sign] fr.

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


24 mars 2022
14h Vincent Despré LORIA
Flipping geometric triangulations on hyperbolic surfaces
We will describe the behavior of the classical Delaunay flip algorithm in the case of hyperbolic surfaces. The complexity of the algorithm depends not only on the number of points of the input triangulation but also on its diameter. Indeed, there are infinitely many different triangulations on a given hyperbolic surfaces with some fixed points. We will give a proof of a polynomial bound for the flip algorithm but also experimental evidences that this bound is largely overestimated. This result can be intuitively explained by the structure of the mapping class group of surfaces.
15h30h Theo Lacombe UGE-LIGM
Transport Optimal : Régularisation Entropique et Homogénéité.
Le problème de transport optimal, dont les origines remontent à Monge, fournit une métrique pour comparer des mesures de probabilités via un problème d'optimisation. Si ce problème possède de nombreuses propriétés théoriques importantes, sa résolution numérique devient rapidement trop lourde et sa limitation aux mesures de probabilités est contraignante. Cet exposé proposera une introduction au problème de transport optimal, d'abord dans sa forme la plus classique, puis dans ses variantes modernes qui font son succès aujourd'hui notamment en apprentissage : la régularisation entropique et le transport déséquilibré. Dans un travail récent [1], T.Séjourné et ses co-auteurs proposent un modèle unifiant ces deux formalismes. Dans certains cas (non-standard), ce nouveau modèle fait apparaître des inhomogénéités qui peuvent mener à des incohérences numériques. Nous ferons la lumière sur ce phénomène et proposerons une correction possible pour obtenir un modèle de transport régularisé déséquilibré homogène, introduit dans [2]. [1] T.Séjourné, J Feydy, FX Vialard, A Trouvé, G Peyré : Sinkhorn divergences for unbalanced optimal transport. [2] TL. An Homogeneous Unbalanced Regularized Optimal Transport model with application to Optimal Transport with Boundary

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

Le comité d'organisation est constitué de Arnaud de Mesmay, Arnau Padrol et Lionel Pournin.