Delaunay triangulations of point sets in closed Euclidean d-manifolds

Manuel Caroli 1 Monique Teillaud 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We give a definition of the Delaunay triangulation of a point set in a closed Euclidean d-manifold, i.e. a compact quo-tient 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 pro-vide an algorithm to compute the Delaunay triangulation of the manifold for a given set of input points, if it exists. Oth-erwise, the algorithm returns the Delaunay triangulation of a finitely-sheeted covering space of the manifold. The al-gorithm has optimal randomized worst-case time and space complexity. Whereas there was prior work for the special case of the flat torus, as far as we know this is the first result for general closed Euclidean d-manifolds. This research is motivated by application fields, like computational biology for instance, showing a need to perform simulations in quotient spaces of the Euclidean space by more general groups of isometries than the groups generated by d independent translations.
Type de document :
Communication dans un congrès
27th Annual Symposium on Computational Geometry, Jun 2011, Paris, France. pp.274-282, 2011, 〈10.1145/1998196.1998236〉
Liste complète des métadonnées

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


https://hal.inria.fr/hal-01101094
Contributeur : Monique Teillaud <>
Soumis le : vendredi 9 janvier 2015 - 13:28:16
Dernière modification le : samedi 27 janvier 2018 - 01:30:57
Document(s) archivé(s) le : vendredi 10 avril 2015 - 10:21:16

Fichiers

hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Manuel Caroli, Monique Teillaud. Delaunay triangulations of point sets in closed Euclidean d-manifolds. 27th Annual Symposium on Computational Geometry, Jun 2011, Paris, France. pp.274-282, 2011, 〈10.1145/1998196.1998236〉. 〈hal-01101094〉

Partager

Métriques

Consultations de la notice

266

Téléchargements de fichiers

157