Choudhary Aruni, Kerber Michael, Raghvendra Sharath
Institut für Informatik, Freie Universität Berlin, Berlin, Germany.
Institut für Geometrie, Technische Universität Graz, Graz, Austria.
J Appl Comput Topol. 2021;5(3):425-458. doi: 10.1007/s41468-021-00072-4. Epub 2021 May 15.
Rips complexes are important structures for analyzing topological features of metric spaces. Unfortunately, generating these complexes is expensive because of a combinatorial explosion in the complex size. For points in , we present a scheme to construct a 2-approximation of the filtration of the Rips complex in the -norm, which extends to a -approximation in the Euclidean case. The -skeleton of the resulting approximation has a total size of . The scheme is based on the integer lattice and simplicial complexes based on the barycentric subdivision of the -cube. We extend our result to use cubical complexes in place of simplicial complexes by introducing between complexes. We get the same approximation guarantee as the simplicial case, while reducing the total size of the approximation to only (cubical) cells. There are two novel techniques that we use in this paper. The first is the use of for proving our approximation result. In our application, these are maps which relate the Rips complex and the approximation in a relatively simple manner and greatly reduce the complexity of showing the approximation guarantee. The second technique is what we refer to as , which is a simple trick to improve the approximation ratio under certain conditions.
黎普斯复形是分析度量空间拓扑特征的重要结构。不幸的是，由于复形规模的组合爆炸，生成这些复形成本高昂。对于(\mathbb{R}^d)中的点，我们提出一种方案，用于构造(\ell_p)范数下黎普斯复形过滤的2 - 近似，在欧几里得情形下可扩展为(O(\log n)) - 近似。所得近似的(k) - 骨架的总规模为(O(n^k))。该方案基于整数格以及基于(d) - 立方体重心细分的单纯复形。通过在复形之间引入(\delta)，我们将结果扩展为使用立方体复形代替单纯复形。我们得到与单纯情形相同的近似保证，同时将近似的总规模减少到仅(O(n^k))（立方体）单元。本文使用了两种新技术。第一种是使用(\varphi) - 映射来证明我们的近似结果。在我们的应用中，这些映射以相对简单的方式关联黎普斯复形和近似，极大地降低了证明近似保证的复杂度。第二种技术是我们所谓的(\delta) - 技巧，这是在某些条件下提高近似比率的一个简单技巧。
