Delaunay triangulations of closed Euclidean d-orbifolds - Archive ouverte HAL Access content directly
Journal Articles Discrete and Computational Geometry Year : 2016

Delaunay triangulations of closed Euclidean d-orbifolds

(1) , (2)
1
2

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.
Fichier principal
Vignette du fichier
DCG-final.pdf (899.32 Ko) Télécharger le fichier
Vignette du fichier
grid36dwireframe.png (209.55 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Figure, Image
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01294409 , version 1 (29-03-2016)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More