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.
