Skip to Main content Skip to Navigation

Delaunay triangulation of manifolds

Abstract : We present an algorithmic framework for producing Delaunay triangulations of manifolds. The input to the algorithm is a set of sample points together with coordinate patches indexed by those points. The transition functions between nearby coordinate patches are required to be bi-Lipschitz with a constant close to 1. The primary novelty of the framework is that it can accommodate abstract manifolds that are not presented as submanifolds of Euclidean space. The output is a manifold simplicial complex that is the Delaunay complex of a perturbed set of points on the manifold. The guarantee of a manifold output complex demands no smoothness requirement on the transition functions, beyond the bi-Lipschitz constraint. In the smooth setting, when the transition functions are defined by common coordinate charts, such as the exponential map on a Riemannian manifold, the output manifold is homeomorphic to the original manifold, when the sampling is sufficiently dense.
Document type :
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Ramsay Dyer Connect in order to contact the contributor
Submitted on : Thursday, October 31, 2013 - 9:42:15 PM
Last modification on : Thursday, January 20, 2022 - 5:26:36 PM
Long-term archiving on: : Saturday, February 1, 2014 - 4:32:23 AM


Files produced by the author(s)


  • HAL Id : hal-00879133, version 1
  • ARXIV : 1311.0117



Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh. Delaunay triangulation of manifolds. [Research Report] RR-8389, INRIA. 2013, pp.28. ⟨hal-00879133⟩



Les métriques sont temporairement indisponibles