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 ℓ 1 {\displaystyle \ell _{1}} and ℓ 2 {\displaystyle \ell _{2}} , let C 1 {\displaystyle C_{1}} (resp. C 2 {\displaystyle C_{2}} ) be the multiset of all cornerpoints and cornerlines for ℓ 1 {\displaystyle \ell _{1}} (resp. ℓ 2 {\displaystyle \ell _{2}} ) counted with their multiplicities, augmented by adding a countable infinity of points of the diagonal { ( x , y ) ∈ R 2 : x = y } {\displaystyle \{(x,y)\in \mathbb {R} ^{2}:x=y\}} . The matching distance between ℓ 1 {\displaystyle \ell _{1}} and ℓ 2 {\displaystyle \ell _{2}} is given by d match ( ℓ 1 , ℓ 2 ) = min σ max p ∈ C 1 δ ( p , σ ( p ) ) {\displaystyle d_{\text{match}}(\ell _{1},\ell _{2})=\min _{\sigma }\max _{p\in C_{1}}\delta (p,\sigma (p))} where σ {\displaystyle \sigma } varies among all the bijections between C 1 {\displaystyle C_{1}} and C 2 {\displaystyle C_{2}} and δ ( ( x , y ) , ( x ′ , y ′ ) ) = min { max { | x − x ′ | , | y − y ′ | } , max { y − x 2 , y ′ − x ′ 2 } } . {\displaystyle \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 match {\displaystyle 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 ∞ {\displaystyle 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 Δ {\displaystyle \Delta } . Moreover, the definition of δ {\displaystyle \delta } implies that matching two points of the diagonal has no cost.

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 ℓ 1 {\displaystyle \ell _{1}} and ℓ 2 {\displaystyle \ell _{2}} , let C 1 {\displaystyle C_{1}} (resp. C 2 {\displaystyle C_{2}} ) be the multiset of all cornerpoints and cornerlines for ℓ 1 {\displaystyle \ell _{1}} (resp. ℓ 2 {\displaystyle \ell _{2}} ) counted with their multiplicities, augmented by adding a countable infinity of points of the diagonal { ( x , y ) ∈ R 2 : x = y } {\displaystyle \{(x,y)\in \mathbb {R} ^{2}:x=y\}} .

The matching distance between ℓ 1 {\displaystyle \ell _{1}} and ℓ 2 {\displaystyle \ell _{2}} is given by d match ( ℓ 1 , ℓ 2 ) = min σ max p ∈ C 1 δ ( p , σ ( p ) ) {\displaystyle d_{\text{match}}(\ell _{1},\ell _{2})=\min _{\sigma }\max _{p\in C_{1}}\delta (p,\sigma (p))} where σ {\displaystyle \sigma } varies among all the bijections between C 1 {\displaystyle C_{1}} and C 2 {\displaystyle C_{2}} and

δ ( ( x , y ) , ( x ′ , y ′ ) ) = min { max { | x − x ′ | , | y − y ′ | } , max { y − x 2 , y ′ − x ′ 2 } } . {\displaystyle \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 match {\displaystyle 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 ∞ {\displaystyle 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 Δ {\displaystyle \Delta } . Moreover, the definition of δ {\displaystyle \delta } implies that matching two points of the diagonal has no cost.

See also

[edit]

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

References

[edit]

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.