Delaunay triangulation of manifolds

We present an algorithm for producing Delaunay triangulations of manifolds. The algorithm can accommodate abstract manifolds that are not presented as submanifolds of Euclidean space. Given a set of sample points and an atlas on a compact manifold, a manifold Delaunay complex is produced provided th...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2015-05
Main Authors: Jean-Daniel Boissonnat, Dyer, Ramsay, Ghosh, Arijit
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Delaunay triangulation
Euclidean geometry
Euclidean space
Manifolds (mathematics)
Smoothness
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present an algorithm for producing Delaunay triangulations of manifolds. The algorithm can accommodate abstract manifolds that are not presented as submanifolds of Euclidean space. Given a set of sample points and an atlas on a compact manifold, a manifold Delaunay complex is produced provided the transition functions are bi-Lipschitz with a constant close to 1, and the sample points meet a local density requirement; no smoothness assumptions are required. If the transition functions are smooth, the output is a triangulation of the manifold. The output complex is naturally endowed with a piecewise flat metric which, when the original manifold is Riemannian, is a close approximation of the original Riemannian metric. In this case the ouput complex is also a Delaunay triangulation of its vertices with respect to this piecewise flat metric.
ISSN:2331-8422