Edge Collapse and Persistence of Flag Complexes
| Autor: | Boissonnat, Jean-Daniel, Pritam, Siddharth |
|---|---|
| Přispěvatelé: | Understanding the Shape of Data (DATASHAPE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), ANR-19-P3IA-0002,3IA@cote d'azur,3IA Côte d'Azur(2019), European Project: 339025,EC:FP7:ERC,ERC-2013-ADG,GUDHI(2014) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Topological Data Analysis
Computational Topology [MATH.MATH-AT]Mathematics [math]/Algebraic Topology [math.AT] [MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT] [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Persistent homology Edge Collapse [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] Simple Collapse |
| Zdroj: | SoCG 2020-36th International Symposium on Computational Geometry SoCG 2020-36th International Symposium on Computational Geometry, Jun 2020, Zurich, Switzerland. ⟨10.4230/LIPIcs.SoCG.2020.19⟩ |
| Popis: | 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 ℱ to a smaller flag filtration ℱ^c with the same persistence. Here again, we only use the 1-skeletons of the complexes. The resulting method to compute ℱ^c 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. LIPIcs, Vol. 164, 36th International Symposium on Computational Geometry (SoCG 2020), pages 19:1-19:15 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|