Linear-size approximations to the Vietoris-Rips filtration (Q2391709): Difference between revisions

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)]. Denser 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\). Deletion 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)\)).