DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cai, Chen | ko |
dc.contributor.author | Kim, Woojin | ko |
dc.contributor.author | Mémoli, Facundo | ko |
dc.contributor.author | Wang, Yusu | ko |
dc.date.accessioned | 2023-08-09T09:02:35Z | - |
dc.date.available | 2023-08-09T09:02:35Z | - |
dc.date.created | 2023-07-06 | - |
dc.date.issued | 2020-06-25 | - |
dc.identifier.citation | 36th International Symposium on Computational Geometry, SoCG 2020, pp.26:1 - 26:17 | - |
dc.identifier.uri | http://hdl.handle.net/10203/311363 | - |
dc.description.abstract | 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 Rd 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(n2 log n) time, which can be improved to O(n2α(n)) if X is from a fixed dimensional Euclidean space Rd, where α(n) is the inverse Ackermann function. | - |
dc.language | English | - |
dc.publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing | - |
dc.title | Elder-rule-staircodes for augmented metric spaces | - |
dc.type | Conference | - |
dc.identifier.scopusid | 2-s2.0-85086499656 | - |
dc.type.rims | CONF | - |
dc.citation.beginningpage | 26:1 | - |
dc.citation.endingpage | 26:17 | - |
dc.citation.publicationname | 36th International Symposium on Computational Geometry, SoCG 2020 | - |
dc.identifier.conferencecountry | SZ | - |
dc.identifier.conferencelocation | Virtual | - |
dc.identifier.doi | 10.4230/LIPIcs.SoCG.2020.26 | - |
dc.contributor.localauthor | Kim, Woojin | - |
dc.contributor.nonIdAuthor | Cai, Chen | - |
dc.contributor.nonIdAuthor | Mémoli, Facundo | - |
dc.contributor.nonIdAuthor | Wang, Yusu | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.