Séminaire du LIF
Jeudi 20 mars à 14h - Luminy, Amphi 12
Éric Colin de Verdière
Laboratoire d'Informatique de l'ENS Paris
Système de lacets optimal sur une surface orientable
Toute surface compacte orientable sans bord est, à homéomorphisme près, une sphère ou un g-tore (accolement de g tores, pour un g > 0). Un système (fondamental) de lacets d'un g-tore est un ensemble de lacets simples ayant un point commun v, deux à deux disjoints sauf en v, tel que le découpage de la surface selon ces lacets donne un disque topologique.
On sait calculer des systèmes de lacets d'une surface, ce qui est utile dans plusieurs applications (paramétrisation, maillage, plaquage de textures) ; mais il est souvent souhaitable d'avoir des lacets aussi courts que possible. Dans un cadre où les lacets sont tracés sur le graphe sommets-arêtes d'une surface triangulée, nous présentons un algorithme polynomial qui calcule un système de longueur minimale parmi tous les systèmes d'une classe d'homotopie donnée.
Éric Colin de Verdière et Francis Lazarus. Optimal System of Loops on an Orientable Surface. Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS'02), p. 627-636, novembre 2002. http://www.di.ens.fr/~colin/textes/focs02.pdf
Home page : http://www.di.ens.fr/~colin/