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

Jean-Daniel Boissonnat 1 Clément Maria 1
1 GEOMETRICA - Geometric computing
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.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2014, 70 (3), pp.406-427. <10.007/s00453-014-9887-3>
Liste complète des métadonnées



https://hal.inria.fr/hal-01108416
Contributeur : Jean-Daniel Boissonnat <>
Soumis le : lundi 24 octobre 2016 - 23:29:46
Dernière modification le : jeudi 9 février 2017 - 15:47:37

Fichiers

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

Identifiants

Collections

Citation

Jean-Daniel Boissonnat, Clément Maria. The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes. Algorithmica, Springer Verlag, 2014, 70 (3), pp.406-427. <10.007/s00453-014-9887-3>. <hal-01108416>

Partager

Métriques

Consultations de
la notice

224

Téléchargements du document

164