Computing Height Persistence and Homology Generators in ℝ3 Efficiently
Computing Height Persistence and Homology Generators in ℝ3 Efficiently
复制标题
高效计算 ℝ3 中的高度持久性和同源生成器
DOI：
10.1137/1.9781611975482.164
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
T. Dey
中科院分区：
文献类型：
--
作者：
T. Dey
最近的研究表明，计算线性嵌入R的单纯2-复形K的第一同调群H1（K）的维数与计算稀疏0 − 1矩阵的秩一样困难。这给计算嵌入在R中的复合体的持久性和同调基（生成元）设置了一个主要的障碍，并且在小于二次甚至接近二次的时间内。那么，第三维度呢？已知当K是一个图或曲面，其n个单形线性嵌入在R中时，K上分段线性函数的持久性可以在O（nlog n）时间内计算，并且一组总大小为k的生成元可以在O（n+ k）时间内计算.然而，一般单纯复形K线性嵌入R的问题并没有完全解决。没有一个算法的复杂性比矩阵乘法是已知的这个重要的情况下。我们表明，高度函数的持久性，因此称为高度持久性，可以在O（n log n）的时间内计算。这使得我们可以在O（n log n+ k）时间内计算Hi（K）的基（生成元），i = 1，2，其中k是输出的大小。这大大提高了O（n）的当前最佳界，ω是矩阵乘法的指数。我们实现这些改进的界限，利用最近的结果锯齿持久性计算拓扑结构，新的观察Reeb图，和一些有效的几何数据结构。俄亥俄州州立大学计算机科学与工程系。tamaldey@cse.ohio-state.edu
Recently it has been shown that computing the dimension of the first homology group H1(K) of a simplicial 2-complex K embedded linearly in R is as hard as computing the rank of a sparse 0 − 1 matrix. This puts a major roadblock to computing persistence and a homology basis (generators) for complexes embedded in R and beyond in less than quadratic or even near-quadratic time. But, what about dimension three? It is known that when K is a graph or a surface with n simplices linearly embedded in R, the persistence for piecewise linear functions on K can be computed in O(n log n) time and a set of generators of total size k can be computed in O(n+ k) time . However, the question for general simplicial complexes K linearly embedded in R is not completely settled. No algorithm with a complexity better than that of the matrix multiplication is known for this important case. We show that the persistence for height functions on such complexes, hence called height persistence, can be computed in O(n log n) time. This allows us to compute a basis (generators) of Hi(K), i = 1, 2, in O(n log n+ k) time where k is the size of the output. This improves significantly the current best bound of O(n), ω being the exponent of matrix multiplication. We achieve these improved bounds by leveraging recent results on zigzag persistence in computational topology, new observations about Reeb graphs, and some efficient geometric data structures. ∗Department of Computer Science and Engineering, The Ohio State University. tamaldey@cse.ohio-state.edu