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 [dot-sign] gac [the-funny-at-sign] ens [dot-sign] 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.

23 mars 2017
14h Louis Esperet CNRS, G-SCOP, Grenoble
Box representations of embedded graphs
A box in $\RR^d$ is the cartesian product of $d$ intervals of $\RR$. For instance, a box in $\RR$ is an interval and a box in $\RR^2$ is an axis-parallel rectangle. Representing graphs as intersection graphs of low dimensional boxes (i.e. each vertex corresponds to a box of $\RR^d$ and two vertices are adjacent if and only if their boxes intersect) is an important problem with applications in the study of ecological and sociological networks. In this talk, I will give a gentle introduction to low dimensional box representations of graphs, and in particular explain an interesting connection with the notion of dimension of a partially ordered set. A classical result of Thomassen (1986) states that every planar graph can be represented as intersection graph of boxes in $\RR^3$. I will explain how this result can be extended to graphs embedded in any fixed surface: I will show that every graph of genus $g$ can be represented as the intersection graph of boxes in dimension $\sqrt{g}\log g$, while random graphs provide a lower bound of order $\sqrt{g\log g}$. I will also show that if a graph is embedded in a fixed surface and has no short non-contractible cycles, then it can be represented as the intersection graph of boxes in $\RR^5$.
15h30 Raphaëlle Chaine LIRIS, Université Claude Bernard Lyon 1
Quasi-uniform triangulations for virtual sculpture and super resolution of digitized surfaces
In this talk I will describe how triangulations can be used to track a surface being sculpted interactively with deformation fields. I will focus on the way to embed and to maintain some drawings on this surface or to transform it as an aggregate of small objects such as a sand pile or a swarm of birds. These approaches rely on maintaining a quasi uniform sampling of the surface, while ensuring some visual continuity. Then I will talk about an approach to up-sample a surface from an eneven point set obtained from laser scans. This involves the use of a new descriptor to detect self-similarities that naturally arise on surfaces and to enrich similar areas jointly, independently of the local shape.
20 avr. 2017
Pierre-Guy Plamondon Université Paris-Sud
Combinatoire des triangulations de surfaces
Lionel Pournin LIPN, Université Paris 13
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:

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