Manifold Reconstruction using Tangential Delaunay Complexes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2009

Manifold Reconstruction using Tangential Delaunay Complexes

Jean-Daniel Boissonnat
  • Fonction : Auteur
  • PersonId : 830857
Arijit Ghosh
  • Fonction : Auteur correspondant
  • PersonId : 865421

Connectez-vous pour contacter l'auteur

Résumé

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.
Fichier principal
Vignette du fichier
Reconstruction-report.pdf (594.29 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00440337 , version 1 (10-12-2009)
inria-00440337 , version 2 (16-09-2011)

Identifiants

  • HAL Id : inria-00440337 , version 2

Citer

Jean-Daniel Boissonnat, Arijit Ghosh. Manifold Reconstruction using Tangential Delaunay Complexes. [Research Report] RR-7142, INRIA. 2009. ⟨inria-00440337v2⟩
233 Consultations
484 Téléchargements

Partager

Gmail Facebook X LinkedIn More