An obstruction to Delaunay triangulations in Riemannian manifolds

DOI10.1007/S00454-017-9908-5zbMATH Open1384.52013arXiv1612.02905OpenAlexW2963365011WikidataQ115387995 ScholiaQ115387995MaRDI QIDQ1702353FDOQ1702353

Arijit Ghosh, Nikolay N. Martynchuk, Ramsay Dyer, Jean-Daniel Boissonnat

Publication date: 28 February 2018

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: Delaunay has shown that the Delaunay complex of a finite set of points $P$ of Euclidean space $mathbb{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.

Full work available at URL: https://arxiv.org/abs/1612.02905

Recommendations

• Delaunay triangulation of manifolds
• scientific article; zbMATH DE number 2119653
• Stability of Delaunay-type structures for manifolds (extended abstract)
• A weak characterisation of the Delaunay triangulation
• Delaunay triangulations of closed Euclidean \(d\)-orbifolds

zbMATH Keywords

triangulationRiemannian manifoldDelaunay complex

Mathematics Subject Classification ID

Polyhedral manifolds (52B70) Local Riemannian geometry (53B20) Quotient spaces, decompositions in general topology (54B15) Triangulating (57R05)

Cites Work

• Manifold reconstruction in arbitrary dimensions using witness complexes
• Bregman Voronoi diagrams
• Riemannian geometry. A modern introduction
• Building triangulations using ε-nets
• Power Diagrams: Properties, Algorithms and Applications
• Delaunay triangulation of manifolds
• Manifold reconstruction from point samples
• A simple triangulation method for smooth manifolds
• Delaunay triangulations and Voronoi diagrams for Riemannian manifolds
• The stability of Delaunay triangulations
• Duals of orphan-free anisotropic Voronoi diagrams are embedded meshes

Cited In (7)

• On groups Gnk and Γnk: A study of manifolds, dynamics, and invariants
• Delaunay triangulations of closed Euclidean \(d\)-orbifolds
• Manifolds of Triangulations, Braid Groups of Manifolds, and the Groups $$\Gamma _{n}^{k}$$
• A manifold of planar triangular meshes with complete Riemannian metric
• Generic families of finite metric spaces with identical or trivial 1-dimensional persistence
• Local criteria for triangulating general manifolds
• Filling triangulated surfaces

This page was built for publication: An obstruction to Delaunay triangulations in Riemannian manifolds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1702353)