Elder-Rule-Staircodes for Augmented Metric Spaces

An augmented metric space is a metric space (X, dX) equipped with a function fX: X → ℝ. This type of data arises commonly in practice, e.g, a point cloud X in ℝd where each point x∈ X has a density function value fX(x) associated to it. An augmented metric space (X, dX, fX) naturally gives rise to a 2-parameter filtration K. However, the resulting 2-parameter persistent homology Hbullet(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 H0(K). Specifically, if n = |X|, the elder-rule-staircode consists of n number of staircase-like blocks in the plane. We show that if H0(K) is interval decomposable, then the barcode of H0(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 H0(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(n2log n) time, which can be improved to O(n2α(n)) if X is from a fixed dimensional Euclidean space ℝd, where α(n) is the inverse Ackermann function.