Computing Bottleneck Distance for Multi-parameter Interval Decomposable Persistence Modules

Abstract

Computation of the interleaving distance between persistence modules is a central task in topological data analysis. For $1$-parameter 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$-parameter persistence modules, $n>1$, because of the well recognized complications of the indecomposables. Here, we consider a reasonably complicated class called {\em $n$-parameter 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 {\em dimension distance} that bounds it from below. An earlier version of this paper considered only the $2$-parameter interval decomposable modules~\cite{DeyCheng18}.

This is the n-parameter extension of the conference paper that appeared in SoCG 2018 (which was only for 2-parameter case)

References in corpus (7)

• The Theory of the Interleaving Distance on Multidimensional Persistence Modules
• Generalized Persistence Diagrams
• Algebraic Stability of Zigzag Persistence Modules
• Stability of higher-dimensional interval decomposable persistence modules
• Computing Bottleneck Distance for Multi-parameter Interval Decomposable Persistence Modules
• Data structures for real multiparameter persistence modules
• Generalized Persistence Algorithm for Decomposing Multi-parameter Persistence Modules

Cited by in corpus (6)

• Spatio-temporal Persistent Homology for Dynamic Metric Spaces
• Computing Bottleneck Distance for Multi-parameter Interval Decomposable Persistence Modules
• Generalized Persistence Algorithm for Decomposing Multi-parameter Persistence Modules
• Elder-Rule-Staircodes for Augmented Metric Spaces
• Capturing Dynamics of Time-Varying Data via Topology
• Local Equivalence of Metrics for Multiparameter Persistence Modules