2026-07-30T07:09:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12184 2024-03-06T10:49:39Z ddc:004 open_access

Elder-Rule-Staircodes for Augmented Metric Spaces Cai, Chen Kim, Woojin Mémoli, Facundo Wang, Yusu Persistent homology Multiparameter persistence Barcodes Elder rule Hierarchical clustering Graded Betti numbers An augmented metric space (X, d_X, f_X) is a metric space (X, d_X) equipped with a function f_X: X → ℝ. It arises commonly in practice, e.g, a point cloud X in ℝ^d where each point x∈ X has a density function value f_X(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, d_X, f_X), 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, d_X, f_X) 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 ℝ^d, where α(n) is the inverse Ackermann function. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chen Cai and Woojin Kim and Facundo Mémoli and Yusu Wang 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.26 urn:nbn:de:0030-drops-121848 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.26 eng https://creativecommons.org/licenses/by/3.0/legalcode