Mardi 04 Octobre 2005, 14h Salle S16 (Passage Saumon, niveau -1)
-
Orateur :
Guenter Rote, Freie Universität Berlin, Institut für Informatik
-
Titre :
Strictly convex drawings of planar graphs
-
Résumé :
Every three-connected planar graph with n vertices has a drawing on an O(n^2) x
O(n^2) grid in which all faces are strictly convex polygons. These drawings are
obtained by perturbing (not strictly) convex drawings on O(n) x O(n) grids. More
generally, a strictly convex drawing exists on a grid of size O(W) x O(n^4/W),
for any choice of a parameter W in the range [n,n^2]. Tighter bounds are
obtained when the faces have fewer sides.
The proof combines combinatorial techniques from graph drawing (in particular,
Schnyder words) with techniques from the geometry of numbers.
joint work with Imre Bárány
Mardi 27 Septembre 2005, 14h Salle S16 (Passage Saumon, niveau -1)
-
Orateur :
Guenter Rote, Freie Universität Berlin, Institut für Informatik
-
Titre :
Counting Polyominoes on Twisted Cylinders
-
Résumé :
Klarner's constant describes the exponential growth rate of the number of
polyominoes (connected subsets of grid squares) with a given number of squares.
It is estimated to be around 4.06, but not even the first digit is known for
sure.
Using numerical methods, we have improved the lower bounds on Klarner's
constant
from 3.87 to 3.98 by analyzing polyominoes on a different surface, a so-called
twisted cylinder, by the transfer matrix method. I will discuss the ingredients
that are involved in this improvement, both from a theoretical and from an
implementation point of view. A bijection for the «states» of partial
solutions
is crucial for allowing a compact representation of the successive iteration
vectors for the transfer matrix method.
joint work with Gill Barequet, Micha Moffie, and Ares Ribó
Mardi 27 Septembre 2005, 15h Salle S16 (Passage Saumon, niveau -1)
-
Orateur :
Eric Colin de Verdière, Liens
-
Titre :
Raccourcissement de courbes non simples sur des surfaces
-
Résumé:
Étant donnée une courbe tracée sur une surface, nous nous intéressons au
problème de calculer la plus courte courbe que l'on peut obtenir par
déformation de la courbe de départ sur la surface. Il est facile de voir
qu'il s'agit d'un problème d'optimisation globale : un lissage local de la
courbe ne suffit pas pour la raccourcir autant que possible.
Nous décrivons des algorithmes de complexité polynomiale pour calculer le
plus court chemin homotope à un chemin donné, ou le plus court cycle
(librement) homotope à un cycle donné, sur une surface combinatoire
orientée. Les algorithmes précédents pour résoudre ce problème, par
Francis Lazarus et moi-même, ne traitaient que le cas des courbes sans
intersections; de plus, leur complexité était connue comme étant
pseudo-polynomiale (polynomiale en la taille de l'entrée et en un paramètre
géométrique de la surface). Nos résultats impliquent aussi que ces
algorithmes ont en fait une complexité en temps polynomiale en la taille de
l'entrée.
Dans le cas d'une surface de complexité n, genre g>1, sans bord, notre
algorithme repose sur le calcul préalable, en temps O(n^2 log n), d'une
décomposition octogonale optimale de la surface: un ensemble de cycles
simples, chacun aussi court que possible dans sa classe d'homotopie, qui
décompose la surface en un assemblage 4-régulier d'octogones. Nous pouvons
ensuite calculer le plus court chemin homotope à un chemin de complexité k
en temps O(gnk), ou le plus court cycle homotope à un cycle de complexité k
en temps O(gnk log(nk)). Un algorithme similaire calcule des plus courtes
courbes homotopes sur des surfaces à bords et/ou de genre 1.
Travail en commun avec Jeff Erickson (Univ. Illinois à Urbana-Champaign),
à paraître à SODA 2006.
Mardi 28 Juin 2005
à 14h00, salle Lingerie (Escalier A, 3ième étage)
-
Orateur :
Luca Castelli Aleardi (LIX)
-
Titre :
Succinct representation of triangulations with a boundary
- Résumé :
We consider the problem of designing succinct geometric data structures
while maintaining efficient navigation operations. A data
structure is said succinct if the asymptotic amount of space it uses
matches the entropy of the class of structures represented.
For the case of planar triangulations with a boundary we propose a
succinct representation of the combinatorial information that
improves to $2.175$ bits per triangle the asymptotic amount of
space required and that supports the navigation between adjacent
triangles in constant time (as well as other standard operations).
For triangulations with $m$ faces of a surface with genus $g$, our
representation requires asymptotically an extra amount of
$36(g-1)\lg m$ bits (which is negligible as long as
$g\ll m/\lg m$).
(joint work with Olivier Devillers and Gilles Schaeffer, to be presented
at WADS 2005)
Mardi 31 Mai 2005
à 14h00, salle Lingerie (Escalier A, 3ième étage)
-
Orateur :
Dominique Attali (CNRS LIS, Grenoble)
-
Titre :
Formules d'inclusion-exclusion à partir de complexes indépendants
- Résumé :
Nous caractérisons les formules minimales d'inclusion-exclusion
obtenues à partir de complexes simpliciaux et permettant de mesurer
l'aire d'une union de disques dans le plan et plus généralement le
volume d'une union de boules dans l'espace euclidien de dimension d.
Ces formules sont décrites par
des triangulations ayant des éléments indépendants et le même espace
sous-jacent que le complexe dual des boules.
Ce problème a des applications en biochimie où une molécule est
souvent identifiée par la portion de l'espace qu'elle occupe. Cette
portion est communément décrite par une union de boules dans
l'espace euclidien tridimensionnel,
chaque boule représentant un atome de la molécule. L'aire
et le volume de cette union interviennent dans le calcul des forces
physiques agissant sur la molécule.
Travail en collaboration avec Herbert Edelsbrunner.
Mardi 24 Mai 2005 à 14h, salle S16 (Passage Saumon, niveau -1)
-
Orateur :
Francis Lazarus (Cnrs Poitiers)
-
Titre :
Immersion combinatoire de courbes sur des surfaces
-
Résumé :
On assiste depuis une quinzaine d'années à un regain
d'intérêt pour des questions algorithmiques portant sur la topologie
des surfaces et plus particulièrement des courbes tracées sur les
surfaces. Parmi les problèmes étudiés on trouve ainsi : le test
d'homotopie entre deux courbes (Dey et Schipper, 1995 et Dey et Guha,
1998), le calcul de systèmes canoniques (Vegter et Yap, 1990), le
calcul de courbe de longueur minimale dans une classe d'homotopie
donnée (Hershberger et Snoeyink, 1994 et Colin de Verdière et Lazarus,
2002), le calcul de système minimal de générateurs pour l'homotopie et
l'homologie (Erickson et Whittlesey, 2005), etc...
La plupart des travaux publiés dans ce domaine s'appuient sur un fond
de topologie générale alors que les résultats obtenus sont
manifestement de nature purement combinatoire. Dans cet exposé nous
développons un cadre formel combinatoire permettant de justifier un
certain nombre de résultats sans faire appel à la topologie. Le cadre
de départ est celui des surfaces combinatoires telles qu'on les
rencontre en théorie topologique des graphes ou en combinatoire
énumérative de cartes. Nous y adjoignons la notion
d'immersion de courbes combinatoires. Nous appliquons ce formalisme à
la classification des surfaces compactes et au calcul de système fondamental
canonique de faible complexité.
L'approche combinatoire présente d'une part l'avantage de preuves plus
simples (les 'monstres' topologiques telles que les 'space filling
curves' n'existent pas dans le monde combinatoire) et ces preuves se
trouvent d'autre part souvent très proches de la programmation finale
des algorithmes.
Mardi 12 avril 2005 à 14h, salle Lingerie (Escalier A, 3ième étage)
-
Orateur:
David Cohen-Steiner (Inria, Sophia-Antipolis)
-
Titre :
Persistance topologique
-
Résumé :
La persistance topologique, introduite par H. Edelsbrunner, D. Letscher et A.
Zomorodian en 2000, est un moyen de distinguer le "signal" du "bruit" dans une
fonction réelle $f$ définie sur un espace topologique. L'idée de la persistance
est d'analyser l'évolution de la topologie des sous-ensembles de niveau
$f^{-1}(-\infty,x]$ de $f$, lorsque le seuil $x$ augmente. Il se trouve que
cette évolution peut être représentée sous la forme d'un ensemble d'intervalles,
appelés intervalles de persistance. Chacun de ces intervalles correspond à la
"durée de vie" d'un événement topologique dans l'évolution des sous-ensembles de niveau de $f$. Une propriété importante de la persistance est sa stabilité vis-à-vis des perturbations. Ainsi, ajouter un bruit de faible amplitude à une fonction réelle aura pour effet d'introduire ou de supprimer des intervalles courts, sans trop modifier les intervalles longs. Les intervalles longs peuvent donc être considérés comme relevant du signal et non du bruit.
La première partie de cet exposé sera consacrée à la définition
de la persistance topologique. Puis je donnerai un algorithme simple
permettant de calculer les intervalles de persistance d'une fonction
linéaire par morceaux définie sur un complexe simplicial. Enfin,
j'exposerai l'idée de la preuve de la propriété de stabilité de la persistance, et j'en décrirai quelques applications géométriques.
Mardi 19 avril 2005 à 14h, salle Lingerie (Escalier A, 3ième étage)
-
Orateur:
Xavier Goaoc (Inria, Nancy)
-
Titre :
Théorème de type Helly et droites perçantes à des sphères congruentes
-
Résumé :
Le Théorème de Helly énonce qu'une famille de convexes de Rd a une intersection
non vide si toute sous-famille de taille d+1 a une intersection non vide. Plus
généralement, les résultats du type "si toute sous-famille de F de taille (au
plus) k a la propriete P alors F a la propriete Q" sont nommés "théorèmes de
type Helly" et font l'objet de recherches actives en géométrie combinatoire.
Une droite perçante pour une famille F d'objets de Rd est une droite qui
intersecte chacun des objets de F. Au cours des dernières décennies, plusieurs
théorèmes de type Helly portant sur l'existence de droites perçantes à des
objets du plan ont été établis. En particulier, Hadwiger a montré en 1957 que si
une famille ordonnée de convexes F est telle que tout triplet admette une droite
perçante compatible avec son ordre alors F admet une droite perçante. En 1958,
Grünbaum a conjecturé l'existence d'un résultat analogue sans restriction sur
l'ordre, non pas dans le cas de convexes généraux mais pour les familles de
copies disjointes d'un même convexe. Cette conjecture ne fut établie qu'en 1989
par Tverberg qui montra que le nombre de Helly est en l'occurence 5.
En dimension 3, Holmsen et Matousek ont établi en 2004 qu'il ne peut exister ni
Théorème de type Helly ni Théorème de Hadwiger pour des convexes généraux, ni
mêmes pour des copies disjointes d'un même convexe. Néanmoins, Holmsen et al.
ont montré en 2003 l'existence de tels résultats dans le cas particulier de
sphères disjointes et congruentes, i.e. de même rayon. Ils ont établi que le
nombre de Hadwiger correspondant est au plus 12 et le nombre de Helly au plus
46, les bornes inférieures correspondantes étant respectivement 4 et 5. En
obtenant de nouveaux résultats sur les permutations géométriques de sphères
congruentes, Cheong et al. ont amélioré en 2003 les bornes supérieures sur les
nombres de Hadwiger et de Helly à respectivement 9 et 18.
Je présenterai une nouvelle preuve des Théorèmes de Hadwiger et de Helly pour
droites perçantes à des sphères congruentes. Cette preuve repose sur une étude
des propriétés des ensembles de droites perçant des sphères afin de leur
appliquer la version topologique du Théorème de Helly et montre que le nombre de
Hadwiger est au plus 6 et celui de Helly au plus 11. Ces résultats ont été
obtenus en collaboration avec Otfried Cheong et Andreas Holmsen.
Mercredi 30 Mars à 14h, salle Lingerie (Escalier A, 3ième étage)
-
Orateur:
Andreas Fabri (GeometryFactory, Grasse)
-
Titre :
CGAL et la GeometryFactory
-
Résumé :
CGAL est une bibliothèque C++ modulaire composée de structures de
données et d'algorithmes géométriques tels que : divers types de
triangulations 2D et 3D, des diagrammes de Voronoï, calculs d'axe
médian, recherche spatiale, opérations booléennes sur les polygones et
les polyèdres, enveloppes convexes, plus courts chemins dans des
polygones, décomposition de polygones, reconstruction de surfaces
polyédriques, etc.
CGAL est développée par le Projet Open Source CGAL (www.cgal.org) qui
regroupe plusieurs instituts de recherche internationaux, dont la
mission est de mettre à disposition des utilisateurs industriels et
académiques les plus importantes solutions et méthodes développées par
la géométrie algorithmique.
Cette bibliothèque est distribuée depuis 1997 et ses utilisateurs
viennent de domaines d'applications aussi divers que le médical, les
traitements d'images aériennes, la géophysique, la CAO, la génération
de maillages, la biochimie, etc.
CGAL est disponible sous licence Open Source et les licences
commerciales peuvent être obtenues via GeometryFactory Sarl,
le start up du projet CGAL. La GeometryFactory a des accords
commercias avec les membres fondateurs du projet CGAL, et avec
de nouveaux membres comme l' ENS/CNRS et New York University.
La présentation couvrira les aspects techniques (géométrie
algorithmique, paradigme de la programmation générique, paradigme du
calcul exact), les aspects organisationnels du projet Open Source, et
les attentes des utilisateurs commerciaux.
Mardi 15 Mars 2005
à 14h00, salle Lingerie (Escalier A, 3ième étage)
-
Orateur :
P. Ossona de Mendez (CNRS UMR 8557, Paris)
-
Titre :
Toucher et Croiser
- Résumé :
Les contacts et les intersections d'objets du plan ont été à
l'origine de nombreuses études, posant des problèmes étonnamment
complexes, bien que faciles à énoncer. Il y a vingt ans, Scheinerman
émit l'hypothèse que tout graphe planaire pouvait être représenté par un
graphe d'intersection de segments (les segments représentant les sommets
et les intersections les arêtes). Cette conjecture est toujours ouverte,
même dans le cas de pseudo-segments. Néanmoins, des résultats partiels
ont été obtenus:
-
1991: les graphes planaires bipartis sont des graphes de contact
de segments en 2 directions,
-
1999: les graphes planaires 4-coloriés sans cycles séparateurs de
longueur 4 recevant 4 couleurs sont des graphes d'intersection de
pseudo-segments,
-
2002: les graphes planaires sans triangles sont des graphes
d'intersection de segments en 3 directions,
-
2004: les graphes planaires 4-coloriés sans cycles séparateurs de
longueur 4 recevant 4 couleurs sont des graphes d'intersection de
segments.
Ce dernier résultat, dont la démonstration sera esquissée ici, a été
découpée en trois publications, la première étant le résultat de 1999.
Elle fait intervenir de nombreux outils et techniques issus notamment de
l'analyse combinatoire, de la topologie et de l'algèbre linéaire, et
nécessite autant de changements de points de vue, pour ne pas dire de
formalismes. C'est cette richesse d'approches qui guidera l'exposé.