Volume 38, Issue 2
A New Approximation Algorithm for the Matching Distance in Multidimensional Persistence

Andrea Cerri & Patrizio Frosini

J. Comp. Math., 38 (2020), pp. 291-309.

Published online: 2020-02

Preview Purchase PDF 15 3077
Export citation
  • Abstract

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 functions, and a distance to compare them, the so-called multidimensional matching distance.
In this paper we propose a new computational framework to deal with the multidimensional matching distance. We start by proving some new theoretical results, and then we use them to formulate an algorithm for computing such a distance up to an arbitrary threshold error.

  • Keywords

Multidimensional persistent topology, Matching distance, Shape comparison.

  • AMS Subject Headings

65D18, 68U05, 55N99

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

acerri@fomsoftware.com (Andrea Cerri)

patrizio.frosini@unibo.it (Patrizio Frosini)

  • BibTex
  • RIS
  • TXT
@Article{JCM-38-291, author = {Cerri , Andrea and Frosini , Patrizio }, title = {A New Approximation Algorithm for the Matching Distance in Multidimensional Persistence}, journal = {Journal of Computational Mathematics}, year = {2020}, volume = {38}, number = {2}, pages = {291--309}, abstract = {

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 functions, and a distance to compare them, the so-called multidimensional matching distance.
In this paper we propose a new computational framework to deal with the multidimensional matching distance. We start by proving some new theoretical results, and then we use them to formulate an algorithm for computing such a distance up to an arbitrary threshold error.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1809-m2018-0043}, url = {http://global-sci.org/intro/article_detail/jcm/14518.html} }
TY - JOUR T1 - A New Approximation Algorithm for the Matching Distance in Multidimensional Persistence AU - Cerri , Andrea AU - Frosini , Patrizio JO - Journal of Computational Mathematics VL - 2 SP - 291 EP - 309 PY - 2020 DA - 2020/02 SN - 38 DO - http://doi.org/10.4208/jcm.1809-m2018-0043 UR - https://global-sci.org/intro/article_detail/jcm/14518.html KW - Multidimensional persistent topology, Matching distance, Shape comparison. AB -

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 functions, and a distance to compare them, the so-called multidimensional matching distance.
In this paper we propose a new computational framework to deal with the multidimensional matching distance. We start by proving some new theoretical results, and then we use them to formulate an algorithm for computing such a distance up to an arbitrary threshold error.

Andrea Cerri & Patrizio Frosini. (2020). A New Approximation Algorithm for the Matching Distance in Multidimensional Persistence. Journal of Computational Mathematics. 38 (2). 291-309. doi:10.4208/jcm.1809-m2018-0043
Copy to clipboard
The citation has been copied to your clipboard