Published:
[Erscheinungsort nicht ermittelbar]: Banff International Research Station (BIRS) for Mathematical Innovation and Discovery, 2018
Published in:Multiparameter Persistent Homology (18w5140) ; (Jan. 2018)
Extent:
1 Online-Ressource (100 MB, 00:28:40:12)
Language:
English
DOI:
10.5446/60560
Identifier:
Origination:
Footnote:
Audiovisuelles Material
Description:
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 {\em 2-D interval decomposable} modules whose indecomposables may have a description of non-constant complexity. We present a polynomial time algorithm to compute the interleaving distance between two such indecomposables. This leads to a polynomial time algorithm for computing the bottleneck distance between two 2-D interval decomposable modules, which bounds their interleaving distance from above. We give another algorithm to compute a new distance called {\em dimension distance} that bounds it from below