hal-00707901, version 1

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

Jean-Daniel Boissonnat () ¹, Clément Maria (, ) ^1, 2

N° RR-7993 (2012)

• 1:  GEOMETRICA (INRIA Sophia Antipolis)
• 
  INRIA France
• 2:  Ecole Normale Supérieure de Cachan (ENS Cachan)
• http://www.ens-cachan.fr/
  École normale supérieure de Cachan - ENS Cachan ENS Cachan 61 Avenue du Président Wilson 94230 Cachan France

Available versions :  v1 (2012-06-15) v2 (2012-07-02)

Bibliographic reference

• Type of document: Research reports
• Domain: Computer Science/Computational Geometry
• Title: The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes
• 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 implement 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.
• Abstract in french: Nous définissons dans cet article une nouvelle structure de données, appelée ''simplex tree'', pour représenter les complexes simpliciaux abstraits de toutes dimensions. Le complexe simplicial est représenté par un arbre préfixe dont les nœuds sont en bijection avec les faces du complexe. Cette structure de données permet de calculer efficacement un grand nombre d'opérations de bases sur les complexes simpliciaux. Nous développons dans cet article une analyse théorique de la complexité de ces algorithmes, ainsi qu'une analyse expérimentale détaillée. Nous étudions plus particulièrement la construction des complexes de Rips et des witness complexes.
• Full text language: English
• Report type: Research Report
• Page number: 20
• Publication date: 2012-06-13
• Keywords: simplicial complexes – data structure – flag complexes – Rips complexes – witness complexes – relaxed witness complexes – high dimensions
• Internal note: RR-7993

Attached file list to this document: 

• hal-00707901, version 1
• http://hal.inria.fr/hal-00707901
• oai:hal.inria.fr:hal-00707901
• From: Clément Maria <>
• Submitted on: Thursday, 14 June 2012 16:51:45
• Updated on: Friday, 22 June 2012 14:30:23