Towards Persistence-Based Reconstruction in Euclidean Spaces - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2008

Towards Persistence-Based Reconstruction in Euclidean Spaces

Frédéric Chazal
Steve Y. Oudot
  • Fonction : Auteur correspondant
  • PersonId : 845393

Connectez-vous pour contacter l'auteur

Résumé

Manifold reconstruction has been extensively studied for the last decade or so, especially in two and three dimensions. Recently, significant improvements were made in higher dimensions, leading to new methods to reconstruct large classes of compact subsets of Euclidean space $\R^d$. However, the complexities of these methods scale up exponentially with d, which makes them impractical in medium or high dimensions, even for handling low-dimensional submanifolds. In this paper, we introduce a novel approach that stands in-between classical reconstruction and topological estimation, and whose complexity scales up with the intrinsic dimension of the data. Specifically, when the data points are sufficiently densely sampled from a smooth $m$-submanifold of $\R^d$, our method retrieves the homology of the submanifold in time at most $c(m)n^5$, where $n$ is the size of the input and $c(m)$ is a constant depending solely on $m$. It can also provably well handle a wide range of compact subsets of $\R^d$, though with worse complexities. Along the way to proving the correctness of our algorithm, we obtain new results on \v Cech, Rips, and witness complex filtrations in Euclidean spaces.
Fichier principal
Vignette du fichier
RR-6391.pdf (391.37 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00197543 , version 1 (16-12-2007)
inria-00197543 , version 2 (17-12-2007)
inria-00197543 , version 3 (18-12-2007)

Identifiants

  • HAL Id : inria-00197543 , version 3
  • ARXIV : 0712.2638

Citer

Frédéric Chazal, Steve Y. Oudot. Towards Persistence-Based Reconstruction in Euclidean Spaces. [Research Report] RR-6391, INRIA. 2008. ⟨inria-00197543v3⟩
488 Consultations
461 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More