Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Edge Collapse and Persistence of Flag Complexes

Jean-Daniel Boissonnat 1 Siddharth Pritam 1
1 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : In this article, we extend the notions of dominated vertex and strong collapse of a simplicial complex as introduced by J. Barmak and E. Miniam. We say that a simplex (of any dimension) is dominated if its link is a simplicial cone. Domination of edges appear to be very powerful and we study it in the case of flag complexes in more detail. We show that edge collapse (removal of dominated edges) in a flag complex can be performed using only the 1-skeleton of the complex. Furthermore, the residual complex is a flag complex as well. Next we show that, similar to the case of strong collapses, we can use edge collapses to reduce a flag filtration F to a smaller flag filtration Fc with the same persistence. Here again, we only use the 1-skeletons of the complexes. The resulting method to compute Fc is simple and extremely efficient and, when used as a preprocessing for Persistence Computation, leads to gains of several orders of magnitude wrt the state-of-the-art methods (including our previous approach using strong collapse). The method is exact, irrespective of dimension, and improves performance of Persistence Computation even in low dimensions. This is demonstrated by numerous experiments on publicly available data.
Complete list of metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/hal-02395227
Contributor : Jean-Daniel Boissonnat <>
Submitted on : Thursday, December 5, 2019 - 12:29:08 PM
Last modification on : Wednesday, January 8, 2020 - 1:35:02 AM
Long-term archiving on: : Friday, March 6, 2020 - 2:38:54 PM

File

socg2020_paper_152.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02395227, version 1

Citation

Jean-Daniel Boissonnat, Siddharth Pritam. Edge Collapse and Persistence of Flag Complexes. 2019. ⟨hal-02395227⟩

Share

Metrics

Record views

146

Files downloads

244