Linear-size approximations to the Vietoris-Rips filtration

DOI10.1007/S00454-013-9513-1MaRDI QIDQ6828420zbMATH OpenFDO

Authors Donald R. Sheehy

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00454-013-9513-1

zbMATH Keywords

net-treespersistent homologyVietoris-Rips filtration

Mathematics Subject Classification ID

Homology and cohomology theories in algebraic topology (55N99) Simplicial sets and complexes in algebraic topology (55U10)

Review text

One of the major challenges of Computational Topology is to extract --- or should we say ``to guess? --- the topology of an object (a subspace of a metric space, say) out of a cloud \(P\) of \(n\) sample points. One tool to this goal is the Vietoris-Rips complex \({\mathcal R}_\alpha\): Its simplices are the sets of points of \(P\) with mutual distance bounded by a fixed value \(\alpha\). Persistent Homology comes into play by varying \(\alpha\): This produces the Vietoris-Rips filtration \({\mathcal R}\) and, as usual, homology classes with longer life are assumed to be meaningful [\textit{G. Carlsson}, Bull. Am. Math. Soc., New Ser. 46, No. 2, 255--308 (2009; Zbl 1172.62002)].\N\NDenser clouds should obviously give better information on the sampled object; still, they produce simplices of high dimension and in great numbers even with very simple objects. This paper offers a clever shortcut: A simple modification of the distance produces an alternative Vietoris-Rips filtration \(\hat{\mathcal R}\) which is proved to be arbitrarily close to the original one. The modified distance makes use of a weight function of \(\alpha\) defined for each point \(p\) of \(P\) and dependent on a deletion time \(t_p\).\N\NDeletion time is determined by organizing \(P\) as a net-tree [\textit{S. Har-Peled} and \textit{M. Mendel}, SIAM J. Comput. 35, No. 5, 1148--1184 (2006; Zbl 1100.68014)] and its use, besides in the definition of the weight, is that a point \(p\) is ignored, when \(\alpha\) exceeds \(t_p\), in the construction of a new zigzag Vietoris-Rips filtration; this is then proved to produce the same persistence diagrams as \(\hat{\mathcal R}\), but with a huge saving of simplices (\(O(n)\)).

Cited in

(7)

• Sparse higher order Čech filtrations
• Effective data reduction algorithm for topological data analysis
• Maximum persistent Betti numbers of Čech complexes
• Computing the multicover bifiltration
• A sparse Delaunay filtration
• A sparse multicover bifiltration of linear size
• Alpha shapes in kernel density estimation

This page was built for publication: Linear-size approximations to the Vietoris-Rips filtration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6828420)