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 : Thursday, January 20, 2022 - 5:27:39 PM


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⟩



Les métriques sont temporairement indisponibles