Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Delaunay Triangulation of Manifolds


Ghosh,  Arijit
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 888KB

Supplementary Material (public)
There is no public supplementary material available

Boissonnat, J.-D., Dyer, R., & Ghosh, A. (2013). Delaunay Triangulation of Manifolds. Retrieved from http://arxiv.org/abs/1311.0117.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-4808-8
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.