#jsDisabledContent { display:none; } My Account | Register | Help

# Matching distance

Article Id: WHEBN0016842914
Reproduction Date:

 Title: Matching distance Author: World Heritage Encyclopedia Language: English Subject: Size theory Collection: Publisher: World Heritage Encyclopedia Publication Date:

### Matching distance

In mathematics, the matching distance[1][2] 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 $\\left\{\left(x,y\right)\in \R^2: x=y\\right\}$.

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

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

Roughly speaking, the matching distance $d_\text\left\{match\right\}$ 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.