The Strange World of the Hausdorff Metric Geometry
II. The Hausdorff metric
A metric is a function that
provides us a way to measure the distance between two objects. More
specifically, a metric d on a space X is a function from X × X
to R (where R represents the set of real numbers) which satisfies the following properties for all x, y,
and z in X:
1. d(x,
y) ≥ 0,
2. d(x,
y) = 0 if and only if x = y,
3. d(x,
y) = d(y, x),
4. d(x,
y) ≤ d(x, z) + d(z, y).
A set X on which a metric d
is defined is called a metric space and is denoted (X, d).
You may have seen the inequality in (4) in other forms. This inequality is
called the triangle inequality. Essentially it says that the shortest distance
between two points is a straight line. A familiar example of a metric is the
standard Euclidean distance function dE between points in Rn.
Of particular interest to us
later will be the case when we obtain equality in the triangle inequality. Note
that in Rn with the Euclidean metric, when three points x, y,
and z satisfy the triangle equality, then the three points all lie on
the same line.
The Hausdorff metric allows us to
measure the distance between certain types of sets. In particular, let H(Rn) denote the space
of all non-empty compact subsets of Rn.
This space is called a hyperspace. In general, compactness in this hyperspace is defined in terms of finite
subcovers of open covers [1]. In Rn, however, compactness
can be characterized in a very simple way - the Heine-Borel Theorem tells us
that compact sets are precisely the closed and bounded subsets of Rn [15].
The Hausdorff metric between two non-empty
compact subsets of Rn can be defined in the following
way.
·
If B is an element of H(Rn), for each x in Rn, we define the distance from x to B
as
d(x, B) = min{dE(x, y)
: y is in B}.
The
following applet illustrates the distance from a point x to a circle B. You can
move the point x with a mouse and
control the center and radius of B by
moving the indicated points.
·
For elements A, B in H(Rn), define the distance from A to B as
d(A, B) = max{d(x, B)
: x is an element of A}.
Note
that d(A,B) is generally
different than d(B, A). Informally, to
find the distance from the set A to the set B, we
find a point a in A that is farthest from B and then
compute the distance from a to the closest point in B.
·
For two elements A, B in H(Rn), the Hausdorff distance, h, between A and B is
h(A, B) = max{d(A, B),
d(B, A)}.
The corresponding metric space, H(Rn),
is then itself a complete metric space [1]. The applet here shows how h(A, B) varies as we alter
the position and radii of two disks A, B in the plane. The colored
line segment (red when h(A, B) = d(A, B)
blue when h(A, B) = d(B, A))
indicates the Hausdorff distance between A and B. You can move
the centers of the disks and control the radii using the points on the
circles.