Delaunay triangulations of closed Euclidean d-orbifolds

Manuel Caroli 1 Monique Teillaud 2, *
* Auteur correspondant
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.
Type de document :
Article dans une revue
Discrete and Computational Geometry, Springer Verlag, 2016, 55 (4), pp.827--853. 〈10.1007/s00454-016-9782-6〉
Liste complète des métadonnées

Littérature citée [53 références]  Voir  Masquer  Télécharger


https://hal.inria.fr/hal-01294409
Contributeur : Monique Teillaud <>
Soumis le : mardi 29 mars 2016 - 11:30:41
Dernière modification le : jeudi 30 novembre 2017 - 09:22:05
Document(s) archivé(s) le : lundi 14 novembre 2016 - 07:24:19

Fichiers

DCG-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

267

Téléchargements de fichiers

140