An Obstruction to Delaunay Triangulations in Riemannian Manifolds

Delaunay has shown that the Delaunay complex of a finite set of points P of Euclidean space R m 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 gen...

Full description

Saved in:
Bibliographic Details
Published in:Discrete & computational geometry 2018, Vol.59 (1), p.226-237
Main Authors: Boissonnat, Jean-Daniel, Dyer, Ramsay, Ghosh, Arijit, Martynchuk, Nikolay
Format: Article
Language:English
Subjects:
Combinatorics
Computational Mathematics and Numerical Analysis
Euclidean geometry
Euclidean space
Manifolds (mathematics)
Mathematics
Mathematics and Statistics
Riemann manifold
Theorems
Triangulation
Voronoi graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Delaunay has shown that the Delaunay complex of a finite set of points P of Euclidean space R m 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.
ISSN:0179-5376
1432-0444
DOI:10.1007/s00454-017-9908-5