Skip to Main content Skip to Navigation
New interface
Journal articles

Delaunay Triangulation of Manifolds

Jean-Daniel Boissonnat 1 Ramsay Dyer 1 Arijit Ghosh 2 
1 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : 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 for a perturbed point set provided the transition functions are bi-Lipschitz with a constant close to 1, and the original 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 output complex is also a Delaunay triangulation of its vertices with respect to this piecewise flat metric.
Document type :
Journal articles
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Jean-Daniel Boissonnat Connect in order to contact the contributor
Submitted on : Tuesday, April 18, 2017 - 4:31:15 PM
Last modification on : Friday, November 4, 2022 - 3:02:51 PM
Long-term archiving on: : Wednesday, July 19, 2017 - 3:29:02 PM


Files produced by the author(s)



Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh. Delaunay Triangulation of Manifolds. Foundations of Computational Mathematics, 2017, 45, pp.38. ⟨10.1007/s10208-017-9344-1⟩. ⟨hal-01509888⟩



Record views


Files downloads