Edge Collapse and Persistence of Flag Complexes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Edge Collapse and Persistence of Flag Complexes

Jean-Daniel Boissonnat
  • Fonction : Auteur
  • PersonId : 830857
Siddharth Pritam
  • Fonction : Auteur
  • PersonId : 1036951

Résumé

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.
Fichier principal
Vignette du fichier
socg2020-edge-collapse-Lipics.pdf (536.6 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02873740 , version 1 (18-06-2020)

Identifiants

Citer

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⟩
573 Consultations
661 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More