Skip to Main content Skip to Navigation
Reports

Manifold Reconstruction using Tangential Delaunay Complexes

Jean-Daniel Boissonnat 1 Arijit Ghosh 1, *
* Corresponding author
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, 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 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.
Document type :
Reports
Complete list of metadatas

Cited literature [42 references]  Display  Hide  Download

https://hal.inria.fr/inria-00440337
Contributor : Arijit Ghosh <>
Submitted on : Friday, September 16, 2011 - 2:56:24 PM
Last modification on : Tuesday, June 18, 2019 - 3:38:04 PM
Long-term archiving on: : Sunday, December 4, 2016 - 8:20:16 PM

File

Reconstruction-report.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00440337, version 2

Collections

Citation

Jean-Daniel Boissonnat, Arijit Ghosh. Manifold Reconstruction using Tangential Delaunay Complexes. [Research Report] RR-7142, INRIA. 2009. ⟨inria-00440337v2⟩

Share

Metrics

Record views

422

Files downloads

478