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 :
Reports
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-00879133
Contributor : Ramsay Dyer <>
Submitted on : Thursday, October 31, 2013 - 9:42:15 PM
Last modification on : Tuesday, April 30, 2019 - 5:14:02 PM
Long-term archiving on : Saturday, February 1, 2014 - 4:32:23 AM

Files

RR-8389.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

741

Files downloads

669