Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Matching distance

Wikipedia contributorsAdapted for Fathomly · View authors
1 min read
Source updated December 9, 2018

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.

Example: The matching distance between and is given by
Example: The matching distance between and is given by
Watch videos about Matching distanceExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Matching distance”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Size theory

In mathematics, size theory studies the properties of topological spaces endowed with R k {\displaystyle \mathbb {R} ^{k}} -valued functions, with respect to the change of these functions. More formally, the subject of size theory is the study of the natural pseudodistance between size pairs.

Size function

Size functions are shape descriptors, in a geometrical/topological sense. They are functions from the half-plane x < y {\displaystyle x<y} to the natural numbers, counting certain connected components of a topological space.

Size functor

Given a size pair {\displaystyle (M,f)\ } where M {\displaystyle M\ } is a manifold of dimension n {\displaystyle n\ } and f {\displaystyle f\ } is an arbitrary real continuous function defined on it, the i {\displaystyle i} -th size functor, with i = 0 , … , n {\displaystyle i=0,\ldots ,n\ } , denoted by F i {\displaystyle F_{i}\ } , is the functor in F u n ( R o r d , A b ) {\displaystyle Fun(\mathrm {Rord} ,\mathrm {Ab} )\ } , where R o r d {\displaystyle \mathrm {Rord} \ } is the category of ordered real numbers, and A b {\displaystyle \mathrm {Ab} \ } is the category of Abelian groups, defined in the following way. For x ≤ y {\displaystyle x\leq y\ } , setting M x = { p ∈ M : f ( p ) ≤ x } {\displaystyle M_{x}=\{p\in M:f(p)\leq x\}\ } , M y = { p ∈ M : f ( p ) ≤ y } {\displaystyle M_{y}=\{p\in M:f(p)\leq y\}\ } , j x y {\displaystyle j_{xy}\ } equal to the inclusion from M x {\displaystyle M_{x}\ } into M y {\displaystyle M_{y}\ } , and k x y {\displaystyle k_{xy}\ } equal to the morphism in R o r d {\displaystyle \mathrm {Rord} \ } from x {\displaystyle x\ } to y {\displaystyle y\ } , for each x ∈ R {\displaystyle x\in \mathbb {R} \ } , F i ( x ) = H i ( M x ) ; {\displaystyle F_{i}(x)=H_{i}(M_{x});\ } F i ( k x y ) = H i ( j x y ) .