Skip to Main content Skip to Navigation
New interface
Conference papers

Computing Persistent Homology of Flag Complexes via Strong Collapses

Jean-Daniel Boissonnat 1, 2 Siddharth Pritam 1, 2 
1 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : In this article, we focus on the problem of computing Persistent Homology of a flag tower, i.e. a sequence of flag complexes connected by simplicial maps. We show that if we restrict the class of simplicial complexes to flag complexes, we can achieve decisive improvement in terms of time and space complexities with respect to previous work. We show that strong collapses of flag complexes can be computed in time O(k^2 v^2) where v is the number of vertices of the complex and k is the maximal degree of its graph. Moreover we can strong collapse a flag complex knowing only its 1-skeleton and the resulting complex is also a flag complex. When we strong collapse the complexes in a flag tower, we obtain a reduced sequence that is also a flag tower we call the core flag tower. We then convert the core flag tower to an equivalent filtration to compute its PH. Here again, we only use the 1-skeletons of the complexes. The resulting method is simple and extremely efficient.
Complete list of metadata

Cited literature [51 references]  Display  Hide  Download
Contributor : Jean-Daniel Boissonnat Connect in order to contact the contributor
Submitted on : Monday, March 25, 2019 - 11:14:25 AM
Last modification on : Friday, February 4, 2022 - 3:20:06 AM
Long-term archiving on: : Wednesday, June 26, 2019 - 1:11:26 PM


Files produced by the author(s)



Jean-Daniel Boissonnat, Siddharth Pritam. Computing Persistent Homology of Flag Complexes via Strong Collapses. SoCG 2019 - International Symposium on Computational geometry, Apr 2019, Portland, United States. ⟨10.4230/LIPIcs.SoCG.2019.55⟩. ⟨hal-02078311⟩



Record views


Files downloads