The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes

Jean-Daniel Boissonnat 1, 2 Clément Maria 2, 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
2 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : This paper introduces a new data structure, called simplex tree, to represent abstract simplicial complexes of any dimension. All faces of the simplicial complex are explicitly stored in a trie whose nodes are in bijection with the faces of the complex. This data structure allows to efficiently imple- ment a large range of basic operations on simplicial complexes. We provide theoretical complexity analysis as well as detailed experimental results. We more specifically study Rips and witness complexes.
Keywords : witness complexes relaxed witness complexes high dimensions topological data analysis flag complexes Rips complexes simplicial complexes data structure computational topology
Type de document :
Communication dans un congrès
Leah Epstein, Paolo Ferragina. 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, Sep 2012, Ljubljana, Slovenia. Springer Berlin Heidelberg, pp.731-742, 2012, Algorithms – ESA 2012. 〈10.1007/978-3-642-33090-2_63〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

simptree.png
simptree.png
simptree.jpg
simptree.jpg
https://hal.inria.fr/hal-01108441
Contributeur : Jean-Daniel Boissonnat <>
Soumis le : vendredi 23 septembre 2016 - 15:25:14
Dernière modification le : samedi 27 janvier 2018 - 01:31:05

Fichiers

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

Identifiants

Collections

INRIA

Citation

Jean-Daniel Boissonnat, Clément Maria. The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes. Leah Epstein, Paolo Ferragina. 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, Sep 2012, Ljubljana, Slovenia. Springer Berlin Heidelberg, pp.731-742, 2012, Algorithms – ESA 2012. 〈10.1007/978-3-642-33090-2_63〉. 〈hal-01108441〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

286

Téléchargements de fichiers

160

Contact


archive-ouverte@inria.fr