Shortening of curves and decomposition of surfaces

Full text

Official version (in French except two chapters in English):

PhD defense

Abstract

The main theme is the shortening of curves on a surface and the decomposition of a surface into topologically elementary surfaces. Let us consider a set of curves drawn on a surface, without intersections or self-intersections. We wish to shorten them as much as possible while preserving their topology, that is, by deforming them continuously without introducing intersections beween them. This is in particular useful in geometric modeling and computer graphics, where finding short topological decompositions is necessary.
We present classical results of topology of surfaces and an overview of the previous works in computational topology of surfaces which are related to this problem. We then provide algorithms to solve it, for embeddings of graphs with fixed vertices and sets of cycles without intersections, in a setting where the curves are drawn on the vertex-edge graph of a polyhedral surface. These algorithms are polynomial in their input and in the ratio between the extreme weights of the edges of the vertex-edge graph. We prove optimality results of each of the resulting curves.

Another work, motivated by the creation of metamorphoses (morphings) between objects, deals with the deformation of triangulations in the plane. We reprove and use Tutte's barycentric embedding theorem to build such deformations, and we prove that its analogue in dimension three does not hold.

A conforming Delaunay triangulation is a Delaunay triangulation of the space which fits the shape of a given polyhedral object. This concept is used in mesh generation. We give an algorithm which computes such a triangulation in dimension three, with a relatively small number of vertices, due to the fact that it adapts to the local geometry of the object.

Keywords: computational topology, homotopy, shortest path, topological decomposition, embedding, graph, parameterization, Delaunay triangulation.

Résumé

Le thème principal est le raccourcissement de courbes sur une surface et la décomposition d'une surface en surfaces topologiquement élémentaires. Considérons des courbes tracées sur une surface, sans intersections ni auto-intersections. Nous souhaitons les raccourcir autant que possible tout en préservant leur topologie, c'est-à-dire en les déformant continûment sans introduire d'intersections. Ceci est en particulier utile en modélisation géométrique et en infographie, où trouver des décompositions topologiques courtes est nécessaire.
Nous présentons des résultats classiques de topologie des surfaces et un survol des travaux antérieurs de topologie algorithmique des surfaces ayant un lien avec ce problème. Nous donnons ensuite des algorithmes pour le résoudre, pour des plongements de graphes à sommets fixés et des ensembles de cycles sans intersections, dans un cadre où les courbes sont tracées sur le graphe sommets-arêtes d'une surface polyédrique. Ces algorithmes sont polynomiaux en leur entrée et en le rapport des poids extrêmes des arêtes du graphe sommets-arêtes. Nous montrons des résultats d'optimalité de chacune des courbes résultantes.

Un autre travail, motivé par la création de métamorphoses (morphings) entre objets, concerne la déformation de triangulations dans le plan. Nous redémontrons et utilisons le théorème de plongement barycentrique de Tutte pour construire de telles déformations, et nous montrons que son analogue en dimension trois est faux.

Une triangulation de Delaunay conforme est une triangulation de Delaunay de l'espace qui épouse la forme d'un objet polyédrique donné. Ce concept est utilisé en génération de maillages. Nous donnons un algorithme qui calcule une telle triangulation en dimension trois, avec un nombre de sommets assez faible, en s'adaptant à la géométrie locale de l'objet.

Mots-clés : topologie algorithmique, homotopie, plus court chemin, décomposition topologique, plongement, graphe, paramétrage, triangulation de Delaunay.