A Note on the Simplex-Tree Construction of the Vietoris-Rips Complex

arXiv2301.07191MaRDI QIDQ6423664FDOQ6423664

Authors: Antonio Rieser 

Publication date: 17 January 2023

Abstract: We give an alternative presentation of the Simplex Tree construction of the Vietoris-Rips complex cite{Boissonnat_Maria_2012}, which highlights how it takes advantage of a small amount of combinatorial structure in the $k$-skeleton of the complex in order to avoid unnecessary comparisons when identifying its $(k+1)$-simplices. We then show that it achieves an order-of-magnitude speedup over the Incremental-VR algorithm in Zomorodian cite{Zomorodian_2010} when constructing the clique complexes of ErdH{o}s-R'enyi graphs.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial aspects of simplicial complexes (05E45) Combinatorics of partially ordered sets (06A07) Topological data analysis (62R40)

This page was built for publication: A Note on the Simplex-Tree Construction of the Vietoris-Rips Complex

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