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