Approximation Algorithm for the Multidimensional Mathching Distance

Topological Persistence has proven to be a promising framework for dealing with problems concerning shape analysis and comparison. In this context, it was originally introduced by taking into account 1-dimensional properties of shapes, modeled by real-valued functions. More recently, Topological Persistence has been generalized to consider multidimensional properties of shapes, coded by vector-valued functions. This extension has led to introduce suitable shape descriptors, named the multidimensional persistence Betti numbers, and a distance to compare them, the socalled multidimensional matching distance. In this paper we propose a new computational framework to deal with the multidimensional matching distance. We start by showing some theoretical results, and then we use them to formulate an algorithm for computing such a distance up to an arbitrary threshold error.