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.


22 juin 2017
14h Boris Bukh Carnegie Mellon University
One-sided epsilon-approximants
[transparents]
Two common approximation notions in discrete geometry are ε-nets and ε-approximants. Of the two, ε-approximants are stronger. For the family of convex sets, small ε-nets exist while small ε-approximants unfortunately do not. In this talk, we introduce a new notion "one-sided ε-approximants", which is of intermediate strength, and prove that small one-sided ε-approximants do exist. The proof is based on a (modification of) the regularity lemma for words by Axenovich--Person--Puzynina. Joint work with Gabriel Nivasch.
15h30 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:

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