Matching distance
# Matching distance

In mathematics, the matching distance is a metric on the space of size functions.

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 \mathbb {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.

