The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes
The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes
复制标题
DOI：
10.1007/s00453-014-9887-3
复制
发表时间：
2014-11-01
期刊：
影响因子：
1.1
通讯作者：
Maria, Clement
中科院分区：
文献类型：
--
作者：
Boissonnat, Jean-Daniel;Maria, Clement
本文引入了一种新的数据结构，称为单纯形树，用于表示任意维的抽象单纯复形。单纯复形的所有面都显式地存储在Trie中，其节点与复形的面是双射的。这种数据结构允许在单纯复形上有效地实现大范围的基本运算。给出了理论上的复杂性分析和详细的实验结果。我们更具体地研究Rips和证人情结。
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.