An Efficient Representation for Filtrations of Simplicial Complexes
An Efficient Representation for Filtrations of Simplicial Complexes
复制标题
单纯复形过滤的有效表示
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
Jean
中科院分区：
文献类型：
--
作者：
Jean
在单纯复形K上的滤过是K的单纯形的一种排序，使得排序中的所有前缀都是K的子复形。过滤是持久同源的核心，持久同源是拓扑数据分析中的主要工具。为了表示单纯复形的过滤，整个过滤可以附加到任何显式存储复形的所有单纯形的数据结构中，例如Hasse图或最近引入的单纯形树。然而，随着需要处理单纯复形的各种计算方法的流行，以及复形大小的快速增加，找到一个仍然可以支持高效查询的紧凑数据结构的任务引起了极大的兴趣。这个方向最近一直在追求的情况下，保持单纯复形。例如，Boissonnat等人[SoCG '15]考虑存储对于包含最大的单形，Attali等人[IJCGA '12]考虑存储阻止复形扩展的单形。然而，到目前为止，还没有一种数据结构可以压缩存储单纯复形的过滤，同时也允许在复形上有效地实现基本操作。在本文中，我们提出了一种新的数据结构，称为临界单纯形图（CSD），它是单纯形数组列表（SAL）的变体[SoCG '15]。我们的数据结构允许以紧凑的方式存储单纯复形的过滤
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