Manifold reconstruction using tangential Delaunay complexes - Archive ouverte HAL Access content directly
Journal Articles Discrete and Computational Geometry Year : 2014

Manifold reconstruction using tangential Delaunay complexes

(1) , (2)
1
2
Jean-Daniel Boissonnat
  • Function : Author
  • PersonId : 935453

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.
Fichier principal
Vignette du fichier
Journal-version.pdf (641.19 Ko) Télécharger le fichier
Vignette du fichier
tangential-complex2.png (45.37 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Figure, Image
Loading...

Dates and versions

hal-00932209 , version 1 (16-01-2014)

Identifiers

Cite

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

Collections

INRIA INRIA2 ANR
376 View
644 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More