Topological Inference via Meshing - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2009

Topological Inference via Meshing

Benoît Hudson
  • Fonction : Auteur
  • PersonId : 865085
Steve Y. Oudot
  • Fonction : Auteur
  • PersonId : 845393

Résumé

We apply ideas from mesh generation to improve the time and space complexities of computing the full persistent homological information associated with a point cloud $P$ in Euclidean space $\R^d$. Classical approaches rely on the \v Cech, Rips, $\alpha$-complex, or witness complex filtrations of $P$, whose complexities scale up very badly with $d$. For instance, the $\alpha$-complex filtration incurs the $n^{\Omega(d)}$ size of the Delaunay triangulation, where $n$ is the size of $P$. The common alternative is to truncate the filtrations when the sizes of the complexes become prohibitive, possibly before discovering the most relevant topological features. In this paper we propose a new collection of filtrations, based on the Delaunay triangulation of a carefully-chosen superset of $P$, whose sizes are reduced to $2^{O(d^2)}n$. A nice property of these filtrations is to be interleaved multiplicatively with the family of offsets of $P$, so that the persistence diagram of $P$ can be approximated in $2^{O(d^2)}n^3$ time in theory, with a near-linear observed running time in practice (ignoring the constant factors depending exponentially on $d$). Thus, our approach remains tractable in medium dimensions, say 4 to 10.
Fichier principal
Vignette du fichier
RR-7125.pdf (652.37 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00436891 , version 1 (01-12-2009)
inria-00436891 , version 2 (01-12-2009)
inria-00436891 , version 3 (03-12-2009)

Identifiants

  • HAL Id : inria-00436891 , version 3

Citer

Benoît Hudson, Gary L. Miller, Steve Y. Oudot, Donald R. Sheehy. Topological Inference via Meshing. [Research Report] RR-7125, INRIA. 2009. ⟨inria-00436891v3⟩
338 Consultations
486 Téléchargements

Partager

Gmail Facebook X LinkedIn More