Triangulating Point Sets in Orbit Spaces

In this work we discuss triangulations of different topological spaces for given point sets. We propose both definitions and algorithms for different classes of spaces and provide an implementation for the specific case of the three-dimensional flat torus. The work is originally motivated by the need for software computing three-dimensional periodic Delaunay triangulations in numerous domains including astronomy, material engineering, biomedical computing, fluid dynamics etc. Periodic triangulations can be under- stood as triangulations of the flat torus. We provide a definition and develop an efficient incremental algorithm to compute Delaunay triangulations of the flat torus. The algorithm is a modification of the incremental algorithm for computing Delaunay triangulations in E^d. Unlike previous work on periodic triangulations we avoid maintaining several periodic copies of the input point set whenever possible. Also the output of our algorithm is guaranteed to always be a triangulation of the flat torus. We provide an implementation of our algorithm that has been made available to a broad public as a part of the Computational Geometry Algorithms Library CGAL. We generalize the work on the flat torus onto a more general class of flat orbit spaces as well as orbit spaces of constant positive curvature. We furthermore consider the much richer class of orbit spaces of constant negative curvature.Dans cette thèse, nous étudions les triangulations définies par un ensemble de points dans des espaces de topologies différentes. Nous proposons une définition générale de la triangulation de Delaunay, valide pour plusieurs classes d'espaces, ainsi qu'un algorithme de construction. Nous fournissons une implantation pour le cas particulier du tore plat tridimensionnel. Ce travail est motivé à l'origine par le besoin de logiciels calculant des triangulations de Delaunay périodiques, dans de nombreux domaines dont l'astronomie, l'ingénierie des matériaux, le calcul biomédical, la dynamique des fluides, etc. Les triangulations périodiques peuvent être vues comme des triangulations du tore plat. Nous fournissons une définition et nous développons un algorithme incrémentiel efficace pour calculer la triangulation de Delaunay dans le tore plat. L'algorithme est adapté de l'algorithme incrémentiel usuel dans R^d. Au contraire des travaux antérieurs sur les triangulations périodiques, nous évitons de maintenir plusieurs copies périodiques des points, lorsque cela est possible. Le résultat fourni par l'algorithme est toujours une triangulation du tore plat. Nous présentons une implantation de notre algorithme, à présent disponible publiquement comme un module de la bibliothèque d'algorithmes géométriques CGAL. Nous généralisons les résultats à une classe plus générale d'espaces quotients plats, ainsi qu'à des espaces quotients de courbure constante positive. Enfin, nous considérons le cas du tore double, qui est un exemple de la classe beaucoup plus riche des espaces quotients de courbure négative constante