An Obstruction to Delaunay Triangulations in Riemannian Manifolds - Archive ouverte HAL Access content directly
Journal Articles Discrete and Computational Geometry Year : 2017

An Obstruction to Delaunay Triangulations in Riemannian Manifolds

(1) , (1) , (2) , (3)
1
2
3

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.
Fichier principal
Vignette du fichier
counterex.pdf (310.67 Ko) Télécharger le fichier
Vignette du fichier
new_three_tets.png (55.93 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Figure, Image
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01583073 , version 1 (06-09-2017)

Identifiers

Cite

Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh, Martynchuk Nikolay. An Obstruction to Delaunay Triangulations in Riemannian Manifolds. Discrete and Computational Geometry, 2017, ⟨10.1145/336154.336221⟩. ⟨hal-01583073⟩
149 View
242 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More