Maps and Distances between Spaces - Mathematical Tools for Shape Analysis and Description - page 49

6.2.1 HAUSDORFF METRIC
e Hausdorff distance between two subsets of a metric space M is the greatest of all the distances
from a point in one subset to the closest point in the other subset. In other words, two subsets are
close in the Hausdorff distance if every point of either subset is close to some point of the other
subset. Formally, the Hausdorff metric (also known as two-sided Hausdorff distance) d H .X;Y/
between two non-empty subsets X and Y of the metric space .M;d/ is defined as:

d H .X;Y/D max f sup
x2X

y2Y d.x;y/; sup
y2Y

inf

x2X d.x;y/g ,

inf (6.2)

where sup represents the supremum and inf the infimum. Due to its relatively easy evaluation,
the Hausdorff distance is very popular for the shape comparison, ranging from images to digital
terrain surfaces to 3D objects. An extension of this concept is provided by the L p -Hausdorff
distance [ 8 ] of which the Hausdorff metric represents the particular case pD1 .

6.2.2 BOTTLENECK DISTANCE
e bottleneck or matching distance between two subsets X , and Y of a metric space M is defined
by:

d m .X;Y/D inf max

x2X d.x;.x//;

(6.3)

where runs over all bijections between X and Y , considered as multisets. A method to compute
the matching distance has been proposed in d'Amico et al. [ 53 ]. Such a measure is useful to
compare sets of points embedded in the metric space; in particular, it is used to compare and
derive stability of persistence diagrams and spaces (see sections 11.2 and 11.3 ).

6.2.3 GROMOV-HAUSDORFF MEASURE
e Gromov-Hausdorff distance casts the comparison of two metric spaces .X;d X / and .Y;d Y /
as a problem of comparing pairwise distances on the spaces (Figure 6.7 ). Notice that in this case,
both the spaces and the distances might differ, e.g., d X could be the Euclidean metric and d Y
the Riemannian metric, etc. Equivalently, the computation of the Gromov-Hausdorff distance
between spaces can be posed as measuring the distortion caused by embedding one metric space
into another, that is, evaluating how much the metric structure is preserved while mapping a
shape into the other. By considering different metrics between points, we get different notions of
metrics between spaces.
Formally, the Gromov-Hausdorff distance [ 92 ], d GH .X;Y/ , between two metric spaces
.X;d X / and .Y;d Y / is defined as

d GH .X;Y/D min
XY ; YX

max .. XY /;. YX /;. XY ; YX // (6.4)

where the distortion . XY / is measured using the maximum distortion induced by the map XY :
. XY /D max jd X .x;y/d Y . XY .x/; XY .y//j