Version officielle (en français sauf deux chapitres en anglais) :
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.
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.
Last modified: Fri Feb 6 14:51:43 MET 2004