Skip to Main content Skip to Navigation
Conference papers

Exact computation of the matching distance on 2-parameter persistence modules

Abstract : The matching distance is a pseudometric on multi-parameter persistence modules, defined in terms of the weighted bottleneck distance on the restriction of the modules to affine lines. It is known that this distance is stable in a reasonable sense, and can be efficiently approximated, which makes it a promising tool for practical applications. In this work, we show that in the 2-parameter setting, the matching distance can be computed exactly in polynomial time. Our approach subdivides the space of affine lines into regions, via a line arrangement. In each region, the matching distance restricts to a simple analytic function, whose maximum is easily computed. As a byproduct, our analysis establishes that the matching distance is a rational number, if the bigrades of the input modules are rational.
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/hal-01966666
Contributor : Steve Oudot <>
Submitted on : Thursday, February 21, 2019 - 1:13:12 PM
Last modification on : Friday, April 30, 2021 - 10:00:36 AM
Long-term archiving on: : Wednesday, May 22, 2019 - 8:14:29 PM

File

p.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01966666, version 1
  • ARXIV : 1812.09085

Citation

Michael Kerber, Michael Lesnick, Steve Oudot. Exact computation of the matching distance on 2-parameter persistence modules. SoCG 2019 - International Symposium on Computational Geometry, Jun 2019, Portland, Oregon, United States. ⟨hal-01966666⟩

Share

Metrics

Record views

101

Files downloads

121