Raccourcissement de courbes non simples sur des surfaces

Eric Colin de Verdière (CNRS, ENS Paris)

Résumé:

Etant 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 initiale sur la surface. Plus précisément, 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 polynomiale en la taille de l'entrée seulement si les poids des arêtes sont uniformes. Nos résultats impliquent aussi que ces algorithmes ont en fait une complexité polynomiale dans tous les cas. Par exemple, dans le cas d'une surface de complexité n, genre g >= 2, sans bord, nous calculons en temps O(n2 log n) des cycles simples, aussi courts que possible dans leur classe d'homotopie, qui décomposent la surface en un assemblage 4-régulier d'octogones. Après ce pré-traitement, nous pouvons calculer un plus court chemin homotope à un chemin de complexité~k en temps O(gnk), ou un plus court cycle homotope à~un cycle de complexité~k en temps O(gnk log(nk)). Des algorithmes similaires calculent 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.