论文标题
增强度量空间的老年规则阶层
Elder-Rule-Staircodes for Augmented Metric Spaces
论文作者
论文摘要
增强度量空间是配备函数$ f_x的度量空间$（x，d_x）$：x \ to \ mathbb {r} $。这种类型的数据通常是在实践中出现的，例如，$ \ mathbb {r}^d $中的点云$ x $，其中每个点$ x \ in x $中的每个点$ x \具有密度函数值$ f_x（x）$与之相关。增强度量空间$（x，d_x，f_x）$自然产生了2个参数过滤$ \ Mathcal {K} $。但是，所得的2-参数持续同源性$ \ mathrm {h} _ {\ bullet}（\ mathcal {k}）$仍然可能是野生表示类型，并且可能不会具有简单的indecosobles。在本文中，由1参数过滤的零零同源性的老年规则激励，我们提出了一个类似条形码的摘要，称为“ Elder-rule-staircode”，作为一种编码$ \ mathrm {h} _0（\ Mathcal {k}）$的编码方式。具体而言，如果$ n = | x | $，则旧规则阶层由$ n $数量的楼梯状块组成。我们表明，如果$ \ mathrm {h} _0（\ mathcal {k}）$是间隔可分解的，则$ \ mathrm {h} _0的条形码（\ mathcal {k}）$等于Elder-rule-staircode。此外，无论间隔可分解性如何，纤维条形码，尺寸函数（又称Hilbert函数）以及$ \ MathRM {H} _0（\ Mathcal {K}）$的分级betti数量都可以有效地计算出Elder-Rule-Staircode。最后，我们开发并实施了一种有效的算法来计算$ o（n^2 \ log n）$时间的老式规则式码，如果$ x $来自固定的eucmentional eucmlidean space $ \ m mathbb {r}^d $，其中$ al}^d $，其中$α$α（n）$α（n）$α（n is Accress），则可以将其提高到$ o（n^2α（n））$。
An augmented metric space is a metric space $(X, d_X)$ equipped with a function $f_X: X \to \mathbb{R}$. This type of data arises commonly in practice, e.g, a point cloud $X$ in $\mathbb{R}^d$ where each point $x\in X$ has a density function value $f_X(x)$ associated to it. An augmented metric space $(X, d_X, f_X)$ naturally gives rise to a 2-parameter filtration $\mathcal{K}$. However, the resulting 2-parameter persistent homology $\mathrm{H}_{\bullet}(\mathcal{K})$ could still be of wild representation type, and may not have simple indecomposables. In this paper, motivated by the elder-rule for the zeroth homology of 1-parameter filtration, we propose a barcode-like summary, called the elder-rule-staircode, as a way to encode $\mathrm{H}_0(\mathcal{K})$. Specifically, if $n = |X|$, the elder-rule-staircode consists of $n$ number of staircase-like blocks in the plane. We show that if $\mathrm{H}_0(\mathcal{K})$ is interval decomposable, then the barcode of $\mathrm{H}_0(\mathcal{K})$ is equal to the elder-rule-staircode. Furthermore, regardless of the interval decomposability, the fibered barcode, the dimension function (a.k.a. the Hilbert function), and the graded Betti numbers of $\mathrm{H}_0(\mathcal{K})$ can all be efficiently computed once the elder-rule-staircode is given. Finally, we develop and implement an efficient algorithm to compute the elder-rule-staircode in $O(n^2\log n)$ time, which can be improved to $O(n^2α(n))$ if $X$ is from a fixed dimensional Euclidean space $\mathbb{R}^d$, where $α(n)$ is the inverse Ackermann function.
