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.

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
Around Sylvester question in the plane
Pick $n$ points uniformly at random in a compact convex body $K$ of the plane. What is the probability $P_{n,K}$ that these points are the vertices of a convex polygon ? (we say, in a convex position). We will discuss exact results existing for the triangle and square (Valtr, and Buchta), and for the disk, as well as asymptotics on $n$. Sylvester problem is the name given to the optimization problem, where the optimization is done on $K$ : for $n=4$ points, the maximum and the minimum are obtained for the disk and triangle (Bläschke). We will see that it is also true for $n=5$, and probably for any $n > 5$ as well.

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.