Résumé:
Étant données des courbes tracées sur une surface, nous souhaitons les raccourcir autant que possible (nous dirons aussi optimiser) en préservant certaines de leurs propriétés topologiques: les courbes obtenues doivent se déduire des courbes initiales par une transformation continue (homotopie ou isotopie).
Ce problème est donc une spécialisation du problème de calcul de plus courts chemins. Il est pertinent en modélisation géométrique et en infographie, notamment pour le paramétrage de surfaces.
Plus spécifiquement, nous voulons optimiser deux types de familles de courbes: un plongement de graphe (famille de chemins simples ne s'intersectant qu'en des extrémités communes) ou une famille de cycles simples et deux à deux disjoints. Nous nous plaçons dans un cadre où toutes les courbes sont tracées sur le graphe sommets-arêtes d'une surface polyédrale.
Nous considérons d'abord des familles de courbes qui ont la particularité de décomposer topologiquement la surface, au sens où le découpage de cette surface le long des courbes donne une union disjointe de surfaces topologiquement élémentaires (disques, cylindres, pantalons); nous donnons des procédés gloutons d'optimisation de telles familles. L'analyse de ces procédés fournit des résultats d'optimalité individuelle de chacune des courbes de la famille résultante. On peut donc optimiser une famille quelconque de courbes en la complétant d'abord en une décomposition topologique de la surface, puis en optimisant celle-ci. Les algorithmes ainsi obtenus ont une complexité polynomiale en leur entrée et en le rapport des poids extrêmes des arêtes du graphe sommets-arêtes.
Travail partiellement en commun avec Francis Lazarus.
Plus de détails: http://www.di.ens.fr/~colin/textes/these.html.fr