Asymptotic Improvements on the Exact Matching Distance for 2-parameter Persistence

In the field of topological data analysis, persistence modules are used to express geometrical features of data sets. The matching distance dM measures the difference between 2-parameter persistence modules by taking the maximum bottleneck distance between 1-parameter slices of the modules. The previous best algorithm to compute dM exactly runs in O(n8+ω) time using O(n4) space, where n is the number of generators and relations of the modules and ω is the matrix multiplication constant. We improve significantly on this by describing an algorithm with expected running time O(n5 log3 n) and using O(n2) space. We first solve the decision problem dM≤ λ for a constant λ in O(n5log n) time by traversing a line arrangement in the dual plane, where each point represents a slice. Then we lift the line arrangement to a plane arrangement in ℝ3 whose vertices represent possible values for dM, and use a randomized incremental method to search through the vertices and find dM. The expected running time of this algorithm is O((n4+T(n))log2 n), where T(n) is an upper bound for the complexity of deciding if dM≤ λ. Moreover, we show how to compute the matching distance using only linear space, to the price of a much worse time complexity.