Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 7 Décembre 1999

Cartes, triangulations et polyedres convexes aléatoires

par Gilles Schaeffer (LORIA Nancy)

Quelques mots, des arbres et des cartes planaires me permettront d'illustrer le lien entre énumeration, codage compact et géneration aléatoire uniforme.

Après avoir defini les cartes combinatoires (ou plongements de graphes dans le plan) et en particulier les triangulations et autres graphes de polyedres convexes, je presenterai deux algorithmes pour construire des triangulations aléatoires.

Enfin, sur l'exemple du diamètre des polyedres convexes, je montrerai comment ces algorithmes permettent de conjecturer des propriétés statistiques.

(Voir aussi sur ma page, le résume étendu Random Sampling of Large Planar Maps and Convex Polyhedra STOC'99, Atlanta.)

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr