Matching distance

In mathematics, the matching distance^[1][2] is a metric on the space of size functions.

Example: The matching distance between $\ell_1=r+a+b$ and $\ell_2=r'+a'$ is given by $d_\text{match}(\ell_1, \ell_2)=\max\{\delta(r,r'),\delta(b,a'),\delta(a,\Delta)\}=4$

The core of the definition of matching distance is the observation that the information contained in a size function can be combinatorially stored in a formal series of lines and points of the plane, called respectively cornerlines and cornerpoints.

Given two size functions $\ell_1$ and $\ell_2$, let $C_1$ (resp. $C_2$) be the multiset of all cornerpoints and cornerlines for $\ell_1$ (resp. $\ell_2$) counted with their multiplicities, augmented by adding a countable infinity of points of the diagonal $\{(x,y)\in \R^2: x=y\}$.

The matching distance between $\ell_1$ and $\ell_2$ is given by $d_\text{match}(\ell_1, \ell_2)=\min_\sigma\max_{p\in C_1}\delta (p,\sigma(p))$ where $\sigma$ varies among all the bijections between $C_1$ and $C_2$ and

$\delta\left((x,y),(x',y')\right)=\min\left\{\max \{|x-x'|,|y-y'|\}, \max\left\{\frac{y-x}{2},\frac{y'-x'}{2}\right\}\right\}.$

Roughly speaking, the matching distance $d_\text{match}$ between two size functions is the minimum, over all the matchings between the cornerpoints of the two size functions, of the maximum of the $L_\infty$-distances between two matched cornerpoints. Since two size functions can have a different number of cornerpoints, these can be also matched to points of the diagonal $\Delta$. Moreover, the definition of $\delta$ implies that matching two points of the diagonal has no cost.

References

1. Michele d'Amico, Patrizio Frosini, Claudia Landi, Using matching distance in Size Theory: a survey, International Journal of Imaging Systems and Technology, 16(5):154–161, 2006.
2. Michele d'Amico, Patrizio Frosini, Claudia Landi, Natural pseudo-distance and optimal matching between reduced size functions, Acta Applicandae Mathematicae, 109(2):527-554, 2010.

See also

• Size theory
• Size function
• Size functor
• Size homotopy group
• Natural pseudodistance