Skip to Main content Skip to Navigation

Triangulating Point Sets in Orbit Spaces

Manuel Caroli 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : 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.
Document type :
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download
Contributor : Manuel Caroli <>
Submitted on : Wednesday, January 5, 2011 - 4:56:31 PM
Last modification on : Saturday, January 27, 2018 - 1:31:24 AM
Long-term archiving on: : Monday, November 5, 2012 - 3:40:20 PM


  • HAL Id : tel-00552215, version 1



Manuel Caroli. Triangulating Point Sets in Orbit Spaces. Computer Science [cs]. Université Nice Sophia Antipolis, 2010. English. ⟨tel-00552215⟩



Record views


Files downloads