2018/12/21 by Kerber, Michael, Lesnick, Michael, Oudot, Steve · 2 citations
#Algebraic Topology (math.AT) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1812.09085
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.