394 G. ELEMENTARY ASPECTS OF METRIC GEOMETRY
(Y, dy) as the infimum, over all metric spaces ( Z, dz) and isometric em-
beddings f : X -+ Z and g : Y -+ Z, of the Hausdorff distance in Z between
f (X) and g (Y), that is,
(G.7) daH ((X, dx), (Y, dy )) ~ inf d~ (f (X), g (Y)),
Z,f,gwhere the infimum is taken over all Z, f, g as above.
The Gromov-Hausdorff distance is a (finite) metric on the set of all
compact metric spaces. In particular, we have that daH is nonnegative,
symmetric, and satisfies the following properties:
(1) If (X, dx) and (Y, dy) are compact metric spaces such that
daH ((X,dx) '(Y,dy)) = 0,
then (X,dx) and (Y,dy) are isometric.
(2) (Triangle inequality)daH ((X, dx)' (Z, dz)) ::::; daH ((X, dx) '(Y, dy )) + daH ((Y, dy)' (Z, dz)).
REMARK G.9. For the proof of (1) see Proposition 3.6 of [78] or Theorem
7.3.30 of [18]. For the proof of (2) see Proposition 7.3.16 of [18] (or Exercise
7.3.26 in [18]).
To give a more intrinsic and computable way to determine the Gromov-
Hausdorff distance, we need a notion to measure how much a map distorts
distances. The distortion of a map f : (X, dx) -+ (Y, dy) is defined by
disf~ sup ldx(x1,x2)-dy(f(x1),f(x2))I
x1,x2EX
(see also Definition 7.1.4 of [18]). Clearly dis f = 0 if and only if f is distance
preserving (i.e., an isometric embedding).
DEFINITION G.10 (c-net). A subset Sofa metric space Xis a called an
c-net if Ne (S) = X, i.e., every point of X is within distance c of S.
We say that a map f : (X,dx) -+ (Y,dy) is an c-isometry (or€-
Hausdorff a.pproximation) if dis f ::::; c and f (X) in an c-net in Y, i.e.,
Ne (f (X)) = Y.
REMARK G .11. The map f in the definition above need not be contin-
uous.
A relation between the Gromov-Hausdorff distance and the distortion
of maps, exact up to factors of 2, is given by the following (see Corollary
7.3.28 of [18]).
LEMMA G.12 (Gromov-Hausdorff distance and c-isometries). Let (X, dx)