Skip to Main content Skip to Navigation
Conference papers

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

Michael Kerber 1 Michael Lesnick 2 Steve Oudot 3 
3 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
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
Contributor : Steve Oudot Connect in order to contact the contributor
Submitted on : Thursday, February 21, 2019 - 1:13:12 PM
Last modification on : Friday, February 4, 2022 - 3:21:46 AM
Long-term archiving on: : Wednesday, May 22, 2019 - 8:14:29 PM


Files produced by the author(s)


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


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⟩



Record views


Files downloads