HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Delaunay triangulations of closed Euclidean d-orbifolds

Manuel Caroli 1 Monique Teillaud 2, *
* Corresponding author
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : We give a definition of the Delaunay triangulation of a point set in a closed Euclidean d-manifold, i.e. a compact quotient space of the Euclidean space for a discrete group of isometries (a so-called Bieberbach group or crystallographic group). We describe a geometric criterion to check whether a partition of the manifold actually forms a triangulation (which subsumes that it is a simplicial complex). We provide an incremental algorithm to compute the Delaunay triangulation of the manifold defined by a given set of input points, if it exists. Otherwise, the algorithm returns the Delaunay triangulation of a finite-sheeted covering space of the manifold. The algorithm has optimal randomized worst-case time and space complexity. It extends to closed Euclidean orbifolds. An implementation for the special case of the 3D flat torus has been released in Cgal 3.5. To the best of our knowledge, this is the first general result on this topic.
Document type :
Journal articles
Complete list of metadata

Cited literature [53 references]  Display  Hide  Download

Contributor : Monique Teillaud Connect in order to contact the contributor
Submitted on : Tuesday, March 29, 2016 - 11:30:41 AM
Last modification on : Wednesday, November 3, 2021 - 7:57:40 AM
Long-term archiving on: : Monday, November 14, 2016 - 7:24:19 AM


Files produced by the author(s)



Manuel Caroli, Monique Teillaud. Delaunay triangulations of closed Euclidean d-orbifolds. Discrete and Computational Geometry, Springer Verlag, 2016, 55 (4), pp.827--853. ⟨10.1007/s00454-016-9782-6⟩. ⟨hal-01294409⟩



Record views


Files downloads