HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

Contributor : Jean-Daniel Boissonnat Connect in order to contact the contributor
Submitted on : Wednesday, September 6, 2017 - 4:38:17 PM
Last modification on : Friday, February 4, 2022 - 3:09:37 AM


Files produced by the author(s)



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⟩



Record views


Files downloads