An obstruction to Delaunay triangulations in Riemannian manifolds

2016/12/09 by Boissonnat, Jean-Daniel, Dyer, Ramsay, Ghosh, Arijit +1
#53B20 (Secondary) #54B15 #57R05 (Primary) #Computational Geometry (cs.CG) #Differential Geometry (math.DG) #FOS: Computer and information sciences #FOS: Mathematics #Geometric Topology (math.GT)

paper · doi:10.48550/arxiv.1612.02905

Abstract

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

Related

• Delaunay triangulation of manifolds
• On the Topology of the Restricted Delaunay Triangulation and Witness Complex in Higher Dimensions
• A weak definition of Delaunay triangulation
• On the Embeddability of Delaunay Triangulations in Anisotropic, Normed, and Bregman Spaces
• Anisotropic triangulations via discrete Riemannian Voronoi diagrams