Elder-Rule-Staircodes for Augmented Metric Spaces

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 $xin 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^2log n)$ time, which can be improved to $O(n^2alpha(n))$ if $X$ is from a fixed dimensional Euclidean space $mathbb{R}^d$, where $alpha(n)$ is the inverse Ackermann function.