2026-07-20T05:04:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8745 2024-03-06T10:42:33Z ddc:004 open_access

Computing Bottleneck Distance for 2-D Interval Decomposable Modules Dey, Tamal K. Xin, Cheng Persistence modules bottleneck distance interleaving distance Computation of the interleaving distance between persistence modules is a central task in topological data analysis. For 1-D persistence modules, thanks to the isometry theorem, this can be done by computing the bottleneck distance with known efficient algorithms. The question is open for most n-D persistence modules, n>1, because of the well recognized complications of the indecomposables. Here, we consider a reasonably complicated class called 2-D interval decomposable modules whose indecomposables may have a description of non-constant complexity. We present a polynomial time algorithm to compute the bottleneck distance for these modules from indecomposables, which bounds the interleaving distance from above, and give another algorithm to compute a new distance called dimension distance that bounds it from below. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tamal K. Dey and Cheng Xin 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.32 urn:nbn:de:0030-drops-87453 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.32 eng https://creativecommons.org/licenses/by/3.0/legalcode