Séminaire de l'équipe Géométrie, Combinatoire et Algorithmes
Département d'Informatique, ENS (Paris)
Pour recevoir ou ne plus recevoir l'annonce du séminaire envoyer un courrier à Michel Pocchiola.
Lundi 25 Mai 2009, 10h30, Salle S16 (passage Saumon, niveau -1)
-
Orateur/Speaker :
Jaroslav Nesetril, Charles University, Prague
-
Titre/Title :
On the Category of Graphs
-
Résumé/Abstract
Despite of the title we hope to demonstrate the richness of the
approach to combinatorial problems using categorical reasoning.
No previous knowledge of CT is necessary.
Lundi 11 Mai 2009, 10h30, Salle INFO 2 (Immeuble Rataud)
-
Orateur/Speaker :
Jaroslav Nesetril, Charles University, Prague
-
Titre/Title :
Constraint Satisfaction and Sparse Structures
-
Résumé/Abstract
How complex are Constraint Satisfaction Problems when restricted to sparse
instances? The answer depends on the notion of sparsity and we shall
survey the recent development in this direction.
Mardi 03 Mars 2009, 14h00, Salle S16 (Passage Saumon, niveau -1)
-
Orateur/Speaker :
Ioannis Emiris, Université d'Athènes
-
Titre/Title :
Implicitisation des courbes et des surfaces paramétrées par des méthodes
combinatoires
-
Résumé/Abstract
Un problème important en modélisation géométrique consiste à déterminer la
forme implicite d'une courbe ou surface, étant donnée sa représentation
paramétrique.
Nous présentons des méthodes pour calculer le support ou, plus
précisément, le polytope de Newton de l'équation implicite, en réduisant
ainsi le problème initial à une question d'algèbre linéaire.
Nos algorithmes
se basent sur la théorie d'élimination creuse et du résultant creux (ou
torique), ce qui nous permet d'exploiter la structure creuse des équations
paramétriques.
Ces méthodes font appel à la géométrie combinatoire, et les
triangulations régulières. On esquisse aussi une approche alternative qui
utilise la géométrie tropicale.
Mardi 07 Octobre 2008, 10h00, Salle Henri Cartan (Passage Saumon, niveau -2)
-
Orateur/Speaker :
Micha Sharir, Tel Aviv University
-
Titre/Title :
Weak epsilon-nets, stabbing interval chains, and Davenport-Schinzel
sequences
-
Résumé/Abstract
We present improved upper bounds for the size of weak epsilon-nets
for convex ranges and point sets in convex position in the plane,
and for points on the moment curve in higher dimensions.
(A weak epsilon-net for a point set P is a set N of points (not
necessarily a subset of P), with the property that the convex hull
of any subset of epsilon*|P| points of P contains a point of N.
The bounds that we derive involve the inverse Ackermann function.
For example, for point sets in convex position in the plane, we
obtain a bound of O(r\alpha(r)) for the size of weak (1/r)-net.
Some nontrivial lower bounds were also obtained, more recently.
The proof is via a reduction to an interesting combinatorial problem
(stabbing interval chains) which apparently has not been studied
before. We provide sharp upper and lower bounds for this problem.
These bounds are suspiciously similar to the bounds on the maximum
length \lambda_s(n) of Davenport-Schinzel sequences.
My Ph.D. student Gabriel Nivasch has followed this cue, and
managed to improve, and essentially tighten, the bounds for
\lambda_s(n) for even values of s. In the process, several new
insights on Davenport-Schinzel sequences were discovered,
including a new formulation of the seqeunces, leading to new
questions and new bounds.
(Joint work with Gabriel Nivasch, Noga Alon, Haim Kaplan, and Shakhar Smorodinsky.)
Lundi 13 Octobre 2008, 14h00, Salle S16 (Passage Saumon, niveau -1)
-
Orateur/Speaker :
Micha Sharir, Tel Aviv University
-
Titre/Title :
Improved bounds and new proofs for epsilon-nets
-
Résumé/Abstract
We present an improved upper bound of O(r\log\log r) for the size of
(standard, "strong") (1/r)-nets (required to be subsets of the given
point set) for points and axis-parallel rectangles in the plane
(or boxes in 3-space). The new paradigm can also be extended to
other instances. This is work in progress, and we are still trying
to understand all the implications of the new technique.
(Joint work with Esther Ezra and Boris Aronov.)
Finally, we have re-examined the old results on the existence of
epsilon-nets of size O(1/epsilon) for halfspaces in two and three
dimensions, and have come up with *many* new and simple proofs.
Again, this is work in progress and we are trying to apply the
new proofs to several new instances as well.
(Joint work with Esther Ezra, Sariel Har-Peled, Haim Kaplan, and
Shakhar Smorodinsky.)
Mardi 23 Septembre 2008, 10h30, Salle S16 (Passage Saumon, niveau -1)
-
Orateur/Speaker :
Vincent Pilaud, Ens
-
Titre:
Énumération des arrangements de cinq double pseudodroites
-
Title :
Enumerating arrangements of five double pseudolines
-
Résumé
Les arrangements de pseudodroites (ou de pseudohyperplans en dimension
supérieure) ont été largement étudiés comme abstraction combinatoire de
configurations de points. Récemment, Habert et Pocchiola ont introduit
les arrangements de double pseudodroites pour étudier les configurations
de convexes disjoints du plan projectif. Les principales propriétés
structurelles des arrangements de pseudodroites (plongeables dans un
plan projectif géométrique, connexité du graphe des mutations,
caractérisation axiomatique) se généralisent aux arrangements de double
pseudodroites.
Pour étudier ces objets et expérimenter des conjectures sur les petits
cas, nous avons implémenté un algorithme incrémental d'énumération des
arrangements mixtes de pseudodroites et double pseudodroites. Nous
présentons l'algorithme et son implémentation.
(travail en commun avec Julien Ferté et Michel Pocchiola)
-
Abstract
Pseudoline arrangements (or in higher dimension, pseudohyperplane
arrangements) have been extensively studied in the last decades as a
useful combinatorial abstraction of configurations of points. Recently,
Habert and Pocchiola introduced double pseudoline arrangements as a
combinatorial abstraction of projective configurations of disjoint
convex bodies. The main structural properties of pseudoline arrangements
(embedability in a geometric projective plane, connectivity of the
mutation graph, axiomatic characterization) extend to double pseudoline
arrangements.
In order to carry out computer experiments, we have implemented an
incremental algorithm to enumerate mixed arrangements, that is, with
both pseudolines and double pseudolines. We present this algorithm and
its implementation.
(joint work with Julien Ferté and Michel Pocchiola)
Les lundis 2, 9 et 16 juin de 13h30 à 15h00,
les mercredis 4, 11 et 18 juin de 11h00 à 12h30, et
les vendredis 6, 13 et 20 juin de 13h30 à 15h00 à l' EHESS, salle 206 (2e étage), 54
bd Raspail 75270, Paris 6e.
Les séances du 16 et du 18 juin sont sous réserve de disponibilité de l'orateur
-
Orateur/Speaker:
Francisco Santos, Santander, Espagne
-
Titre/Title: Triangulations of polytopes
-
Résumé/Abstract :
Triangulations of polytopes play an important role in several parts of
mathematics, both pure and applied. This course is an introduction to
them, focusing in the theory of regular triangulations and secondary
polytopes developed in the last twenty years. We will follow the first
half of the forthcoming book by J. A. de Loera, J. Rambau and F.
Santos, specially chapters 2, 4 and 5. The current version of the book
can be downloaded
here
As prerequisites, a certain familiarity with polyhedral combinatorics
will be helpful, but will not be strictly required.
Mardi 3 Juin 2008, 14h00, Salle S16 (Passage Saumon, niveau -1)
-
Orateur/Speaker :
Luca Castelli Aleardi, ULB
-
Titre/Title :
Schnyder woods for higher genus triangulated surfaces
-
Résumé/Abstract
Lundi 26 mai 2008, 10h30, Salle U/V (niveau -2)
-
Orateur/Speaker :
Guillaume Chapuy
-
Titre/Title :
Sur la structure des cartes à une face
-
Résumé/Abstract
Mercredi 14 mai 2008, 14h30, Salle S16 (Passage Saumon, niveau -1)
-
Orateur/Speaker :
John Harer, Duke University
-
Titre/Title :
Persistent homology - Finding global shape in datasets
-
Résumé/Abstract
Mardi 11 Mars 2008, 14h, Salle S16 (Passage Saumon niveau -1)
-
Orateur/Speaker :
Franck Nielsen, Sony CSL/Ecole Polytechnique
-
Titre/Title :
On the Centroids of Symmetrized Bregman Divergences
-
Résumé/Abstract
Mardi 8 Janvier 2008, 14h, Salle S16 (Passage Saumon niveau -1)
-
Orateur/Speaker :
Éric Colin de Verdière, ENS Paris, CNRS
-
Titre/Title :
Plus courts chemins disjoints dans un graphe planaire
-
Résumé/Abstract
Mardi 20 Novembre 2007, 14h, Salle S16 (Passage Saumon niveau -1)
-
Orateur/Speaker :
Jürgen
Bokowski, TU Darmstadt
-
Titre/Title :
Oriented matroids, i.e., a natural extended equivalence class of matrices,
with applications to polyhedral embeddings and point line configurations
-
Résumé/Abstract
Mardi 06 Novembre 2007, 14h, Salle S16 (Passage Saumon niveau -1)
-
Orateur/Speaker :
Yves Bertot, Inria,
Sophia Antipolis
-
Titre/Title : Formalisation d'algorithmes de géométrie: le cas des enveloppes convexes,
CC-systèmes et contournement des problèmes de dégénérescence
-
Résumé/Abstract
Mardi 16 octobre 2007, 14h, Salle S16 (Passage Saumon niveau -1)
Année 2007
Année 2006
Année 2005
Année 2004
Année 2003