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.
Type de document :
Article dans une revue
Discrete and Computational Geometry, Springer Verlag, 2014, 51 (1), pp.221-267. 〈10.1007/s00454-013-9557-2〉
Liste complète des métadonnées

Littérature citée [39 références]  Voir  Masquer  Télécharger
Contributeur : Jean-Daniel Boissonnat <>
Soumis le : jeudi 16 janvier 2014 - 14:59:23
Dernière modification le : samedi 27 janvier 2018 - 01:30:40
Document(s) archivé(s) le : samedi 8 avril 2017 - 18:30:14


Fichiers produits par l'(les) auteur(s)




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〉



Consultations de la notice


Téléchargements de fichiers