Elder-rule-staircodes for augmented metric spaces

Conference Paper

An augmented metric space (X, dX, fX) is a metric space (X, dX) equipped with a function fX: X → R. It arises commonly in practice, e.g, a point cloud X in R where each point x ∈ X has a density function value fX(x) associated to it. Such an augmented metric space naturally gives rise to a 2-parameter filtration. However, the resulting 2-parameter persistence module 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 a 1-parameter filtration, we propose a barcode-like summary, called the elder-rule-staircode, as a way to encode the zeroth homology of the 2-parameter filtration induced by a finite augmented metric space. Specifically, given a finite (X, dX, fX), its elder-rule-staircode consists of n = |X| number of staircase-like blocks in the plane. We show that the fibered barcode, the fibered merge tree, and the graded Betti numbers associated to the zeroth homology of the 2-parameter filtration induced by (X, dX, fX) can all be efficiently computed once the elder-rule-staircode is given. Furthermore, for certain special cases, this staircode corresponds exactly to the set of indecomposables of the zeroth homology of the 2-parameter filtration. Finally, we develop and implement an efficient algorithm to compute the elder-rule-staircode in O(n log n) time, which can be improved to O(n α(n)) if X is from a fixed dimensional Euclidean space R , where α(n) is the inverse Ackermann function. d 2 2 d

Full Text

Duke Authors

Cited Authors

  • Cai, C; Kim, W; Mémoli, F; Wang, Y

Published Date

  • June 1, 2020

Published In

Volume / Issue

  • 164 /

International Standard Serial Number (ISSN)

  • 1868-8969

International Standard Book Number 13 (ISBN-13)

  • 9783959771436

Digital Object Identifier (DOI)

  • 10.4230/LIPIcs.SoCG.2020.26

Citation Source

  • Scopus