An Efficient Representation for Filtrations of Simplicial Complexes

Jean-Daniel Boissonnat 1 Karthik C. Srikanta 2
1 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : A filtration over a simplicial complex K is an ordering of the simplices of K such that all prefixes in the ordering are subcomplexes of K. Filtrations are at the core of Persistent Homology, a major tool in Topological Data Analysis. In order to represent the filtration of a simplicial complex, the entire filtration can be appended to any data structure that explicitly stores all the simplices of the complex such as the Hasse diagram or the recently introduced Simplex Tree [Algorithmica '14]. However, with the popularity of various computational methods that need to handle simplicial complexes, and with the rapidly increasing size of the complexes, the task of finding a compact data structure that can still support efficient queries is of great interest. This direction has been recently pursued for the case of maintaining simplicial complexes. For instance, Boissonnat et al. [SoCG '15] considered storing the simplices that are maximal for the inclusion and Attali et al. [IJCGA '12] considered storing the simplices that block the expansion of the complex. Nevertheless, so far there has been no data structure that compactly stores the filtration of a simplicial complex, while also allowing the efficient implementation of basic operations on the complex. In this paper, we propose a new data structure called the Critical Simplex Diagram (CSD) which is a variant of the Simplex Array List (SAL) [SoCG '15]. Our data structure allows to store in a compact way the filtration of a simplicial complex, and allows for the efficient implementation of a large range of basic operations. Moreover, we prove that our data structure is essentially optimal with respect to the requisite storage space. Next, we show that the CSD representation admits the following construction algorithms. • A new edge-deletion algorithm for the fast construction of Flag complexes, which only depends on the number of critical simplices and the number of vertices. • A new matrix-parsing algorithm to quickly construct relaxed Delaunay complexes, depending only on the number of witnesses and the dimension of the complex.
Type de document :
Communication dans un congrès
Symposium on Discrete Algorithms SODA 2017, Jan 2017, Barcelona, France. 0005
Liste complète des métadonnées



https://hal.inria.fr/hal-01416683
Contributeur : Jean-Daniel Boissonnat <>
Soumis le : mercredi 14 décembre 2016 - 17:04:26
Dernière modification le : jeudi 15 juin 2017 - 09:08:47
Document(s) archivé(s) le : mercredi 15 mars 2017 - 15:15:49

Fichiers

arxiv.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01416683, version 1

Collections

Citation

Jean-Daniel Boissonnat, Karthik C. Srikanta. An Efficient Representation for Filtrations of Simplicial Complexes. Symposium on Discrete Algorithms SODA 2017, Jan 2017, Barcelona, France. 0005. <hal-01416683>

Partager

Métriques

Consultations de
la notice

381

Téléchargements du document

113