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 metadatas

Cited literature [53 references]  Display  Hide  Download


https://hal.inria.fr/hal-01294409
Contributor : Monique Teillaud <>
Submitted on : Tuesday, March 29, 2016 - 11:30:41 AM
Last modification on : Tuesday, December 18, 2018 - 4:18:26 PM
Long-term archiving on : Monday, November 14, 2016 - 7:24:19 AM

Files

DCG-final.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

582

Files downloads

415