License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.26
URN: urn:nbn:de:0030-drops-121848
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12184/
Cai, Chen ;
Kim, Woojin ;
Mémoli, Facundo ;
Wang, Yusu
Elder-Rule-Staircodes for Augmented Metric Spaces
Abstract
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.
BibTeX - Entry
@InProceedings{cai_et_al:LIPIcs:2020:12184,
author = {Chen Cai and Woojin Kim and Facundo M{\'e}moli and Yusu Wang},
title = {{Elder-Rule-Staircodes for Augmented Metric Spaces}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {26:1--26:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12184},
URN = {urn:nbn:de:0030-drops-121848},
doi = {10.4230/LIPIcs.SoCG.2020.26},
annote = {Keywords: Persistent homology, Multiparameter persistence, Barcodes, Elder rule, Hierarchical clustering, Graded Betti numbers}
}
|
Keywords: |
|
Persistent homology, Multiparameter persistence, Barcodes, Elder rule, Hierarchical clustering, Graded Betti numbers |
|
Collection: |
|
36th International Symposium on Computational Geometry (SoCG 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
08.06.2020 |
