HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Manifold reconstruction using Tangential Delaunay Complexes

Jean-Daniel Boissonnat 1 Arijit Ghosh 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We give a provably correct algorithm to reconstruct a k-dimensional manifold embedded in d-dimensional Euclidean space. Input to our algorithm is a point sample coming from an unknown manifold. Our approach is based on two main ideas : the notion of tangential Delaunay complex defined and the technique of sliver removal by weighting the sample points. Differently from previous methods, we do not construct any subdivision of the embedding d-dimensional space. As a result, the running time of our algorithm depends only linearly on the extrinsic dimen- sion d while it depends quadratically on the size of the input sample, and exponentially on the intrinsic dimension k. To the best of our knowledge, this is the first certified algorithm for manifold reconstruction whose complexity depends lin- early on the ambient dimension. We also prove that for a dense enough sample the output of our algorithm is isotopic to the manifold and a close geometric approximation of the manifold.
Document type :
Conference papers
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download

Contributor : Jean-Daniel Boissonnat Connect in order to contact the contributor
Submitted on : Monday, May 31, 2010 - 12:14:52 PM
Last modification on : Tuesday, December 8, 2020 - 9:41:52 AM
Long-term archiving on: : Thursday, September 16, 2010 - 4:41:58 PM


Files produced by the author(s)


  • HAL Id : hal-00487862, version 1



Jean-Daniel Boissonnat, Arijit Ghosh. Manifold reconstruction using Tangential Delaunay Complexes. ACM Symposium on Computational Geometry, Jun 2010, Snowbird, United States. pp.200. ⟨hal-00487862⟩



Record views


Files downloads