An Obstruction to Delaunay Triangulations in Riemannian Manifolds

Abstract : Delaunay has shown that the Delaunay complex of a finite set of points P of Euclidean space Rm triangulates the convex hull of P, provided that P satisfies a mild genericity property. Voronoi diagrams and Delaunay complexes can be defined for arbitrary Riemannian manifolds. However, Delaunay's genericity assumption no longer guarantees that the Delaunay complex will yield a triangulation; stronger assumptions on P are required. A natural one is to assume that P is sufficiently dense. Although results in this direction have been claimed, we show that sample density alone is insufficient to ensure that the Delaunay complex triangulates a manifold of dimension greater than 2.
Type de document :
Article dans une revue
Discrete and Computational Geometry, Springer Verlag, 2017, 〈10.1145/336154.336221〉
Liste complète des métadonnées

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


https://hal.inria.fr/hal-01583073
Contributeur : Jean-Daniel Boissonnat <>
Soumis le : mercredi 6 septembre 2017 - 16:38:17
Dernière modification le : lundi 9 octobre 2017 - 13:18:03

Fichiers

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

Identifiants

Collections

Citation

Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh, Martynchuk Nikolay. An Obstruction to Delaunay Triangulations in Riemannian Manifolds. Discrete and Computational Geometry, Springer Verlag, 2017, 〈10.1145/336154.336221〉. 〈hal-01583073〉

Partager

Métriques

Consultations de la notice

56

Téléchargements de fichiers

18