Skip to Main content Skip to Navigation
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

https://hal.inria.fr/hal-02078311
Contributor : Jean-Daniel Boissonnat <>
Submitted on : Monday, March 25, 2019 - 11:14:25 AM
Last modification on : Friday, April 30, 2021 - 10:03:13 AM
Long-term archiving on: : Wednesday, June 26, 2019 - 1:11:26 PM

File

PersistenceOfFlagComplexes.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

211

Files downloads

424