Skip to Main content Skip to Navigation
Conference 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 appears to be a very powerful concept, especially when applied to flag complexes. 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 w.r.t 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 metadata

Cited literature [58 references]  Display  Hide  Download

https://hal.inria.fr/hal-02873740
Contributor : Jean-Daniel Boissonnat Connect in order to contact the contributor
Submitted on : Thursday, June 18, 2020 - 3:01:42 PM
Last modification on : Friday, April 30, 2021 - 10:03:13 AM

File

socg2020-edge-collapse-Lipics....
Files produced by the author(s)

Identifiers

Citation

Jean-Daniel Boissonnat, Siddharth Pritam. Edge Collapse and Persistence of Flag Complexes. SoCG 2020 - 36th International Symposium on Computational Geometry, Jun 2020, Zurich, Switzerland. ⟨10.4230/LIPIcs.SoCG.2020.19⟩. ⟨hal-02873740⟩

Share

Metrics

Record views

253

Files downloads

640