Publication

An Obstruction to Delaunay Triangulations in Riemannian Manifolds

Boissonnat, J-D., Dyer, R., Ghosh, A. & Martynchuk, N., Jan-2018, In : Discrete & computational geometry. 59, 1, p. 226-237 12 p.

Research output: Contribution to journalArticleAcademicpeer-review

Copy link to clipboard

Documents

  • An Obstruction to Delaunay Triangulations in Riemannian Manifolds

    Final publisher's version, 497 KB, PDF document

    Request copy

Links

DOI

  • Jean-Daniel Boissonnat
  • Ramsay Dyer
  • Arijit Ghosh
  • Nikolay Martynchuk

Delaunay has shown that the Delaunay complex of a finite set of points of Euclidean space triangulates the convex hull of provided that 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 are required. A natural one is to assume that 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.

Original languageEnglish
Pages (from-to)226-237
Number of pages12
JournalDiscrete & computational geometry
Volume59
Issue number1
Publication statusPublished - Jan-2018

    Keywords

  • Delaunay complex, Triangulation, Riemannian manifold

ID: 76276536