Skip to Main content Skip to Navigation
Journal articles

Manifold reconstruction using tangential Delaunay complexes

Jean-Daniel Boissonnat 1 Arijit Ghosh 2
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 smooth manifold embedded in d-dimensional Euclidean space. The 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 and the technique of sliver removal by weighting the sample points. Differently from previous methods, we do not construct any subdivision of the d-dimensional ambient space. As a result, the running time of our al- gorithm depends only linearly on the extrinsic dimension 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 linearly 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.
Complete list of metadatas

Cited literature [39 references]  Display  Hide  Download


https://hal.inria.fr/hal-00932209
Contributor : Jean-Daniel Boissonnat <>
Submitted on : Thursday, January 16, 2014 - 2:59:23 PM
Last modification on : Tuesday, June 18, 2019 - 3:38:04 PM
Document(s) archivé(s) le : Saturday, April 8, 2017 - 6:30:14 PM

Files

Journal-version.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Jean-Daniel Boissonnat, Arijit Ghosh. Manifold reconstruction using tangential Delaunay complexes. Discrete and Computational Geometry, Springer Verlag, 2014, 51 (1), pp.221-267. ⟨10.1007/s00454-013-9557-2⟩. ⟨hal-00932209⟩

Share

Metrics

Record views

745

Files downloads

901