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

MaRDI QIDQ6423664zbMATH OpenFDO

Authors Antonio Rieser

Publication date 17 January 2023

Mathematics Subject Classification ID

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

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.

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)