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.

Annonce. De mars à juin 2017, Jean-Daniel Boissonnat, titulaire de la chaire "Informatique et sciences numériques" au Collège de France, organise une série de cours et de colloques sur le thème "Géométrie algorithmique : données, modèles, programmes". Voir ici pour les détails.

20 avr. 2017
salle 314 (exceptionnellement)
14h Lionel Pournin LIPN, Université Paris 13
From mesh generation to associahedra and related structures
[transparents]
The flip operation is used in computational geometry to generate meshes or modify them. Depending on the underlying point set, these meshes also give rise, via flips, to structures with deep connections to a number of other fields such as combinatorics, algebra, topology, theoretical physics, and biology. Some of these connections will be described in this talk. One of these connections is with the associahedron, a polytope that pops up in surprisingly different contexts. Another is related to the triangulations of topological surfaces. Several results and open problems will be mentioned along the way. Part of this talk is based on a joint work with Hugo Parlier.
15h30 Pierre-Guy Plamondon Université Paris-Sud
Combinatoire des triangulations de surfaces
L'objectif de cet exposé sera de présenter un survol de certaines propriétés combinatoires et algébriques des triangulations dites décorées (en un sens à définir) de surfaces orientables avec bord et points marqués. La notion de "flip" permettant de passer d'une triangulation à une autre est intimement liée à la notion de "mutation" dans la théorie des algèbres amassées. Après avoir passé en revue des propriétés combinatoires des triangulations, nous étudierons des applications aux algèbres amassées par ce lien.
11 mai 2017
14h Pierre Alliez Inria Sophia-Antipolis — Méditerranée
Inter-surface Mapping via Optimal Mass Transport
Recent advances based on entropic regularization are unleashing the power of optimal transport. In this talk I will present a novel approach for computing a homeomorphic map between two discrete surfaces. While most previous approaches compose maps over intermediate domains which result in suboptimal inter-surface mapping, we directly optimize a map by computing a mass transport plan between two surfaces. This non-linear problem, which amounts to minimizing the Dirichlet energy of both the map and its inverse, is solved using two alternating convex optimization problems in a coarse-to-fine fashion. Computational efficiency is further improved through the use of Sinkhorn iterations, modified to handle minimal regularization and unbalanced transport plans. The resulting inter-surface mapping algorithm applies to arbitrary shapes, with little to no user interaction.

Joint work with David Cohen-Steiner, Manish Mandad, Mathieu Desbrun and Leif Kobbelt.

15h30 Guilherme Dias da Fonseca Université Clermont Auvergne
Geometric Approximation Using a Hierarchy of Macbeath Regions
This talk is divided in two parts, presenting two papers written with Sunil Arya and David M. Mount (SODA 2017 and SoCG 2017). Both papers are based on a new hierarchy of Macbeath regions that approximates a convex body $K$ in $d$-dimensional space up to an error $\epsilon > 0$. For the purpose of the complexity analysis, we assume that $d$ is a constant, but that $\epsilon$ is an asymptotic variable approaching $0$. Out goal is to minimize dependencies on $\epsilon$, for example from $1/\epsilon^d$ to $1/\epsilon^{d/2}$.

In the first part of the talk, we present an optimal data structure to approximately answer if a query point $q$ is inside or outside of $K$. We attain logarithmic query time with storage of only $O(1/\epsilon^{(d-1)/2})$, which matches the worst-case lower bound on the complexity of any $\epsilon$-approximating polytope. Using known reductions, we obtain major improvements to approximate nearest neighbor searching.

In the second part, we show how the hierarchy can be used to construct an $\epsilon$-kernel in near-optimal time. Kernels provide an approximation to the convex hull, and therefore are on the basis of several geometric algorithms. We obtain major improvements to the complexity of other fundamental problems, such as approximate diameter, approximate bichromatic closest pair, and approximate Euclidean minimun bottleneck tree, as well as near-optimal preprocessing times to multiple data structures.

22 juin 2017
Boris Bukh Carnegie Mellon University
Jean-François Marckert CNRS, LaBRI, Université Bordeaux 1

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.