Computing Bottleneck Distance for 2-D Interval Decomposable Modules
Published in 34th International Symposium on Computational Geometry (SoCG), 2018
Abstract
Computation of the interleaving distance between persistence modules is a central task in topological data analysis. For 1-D persistence modules this can be done via bottleneck distance. For most n-D modules (n > 1), complications from indecomposables make this open. We study 2-D interval decomposable modules whose indecomposables may have non-constant complexity. We present a polynomial-time algorithm to compute the bottleneck distance for these modules from indecomposables, giving an upper bound on interleaving distance, and introduce a dimension distance that provides a lower bound.
Key Points
- Focus on 2-D interval decomposable persistence modules with complex indecomposables
- Polynomial-time bottleneck distance algorithm that upper bounds interleaving distance
- New dimension distance providing a complementary lower bound