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 *d _{E}* between points in

Of particular interest to us
later will be the case when we obtain equality in the triangle inequality. Note
that in **R*** ^{n}* with the Euclidean metric, when three points

The Hausdorff metric allows us to
measure the distance between certain types of sets. In particular, let *H*(**R*** ^{n}*) denote the space
of all non-empty compact subsets of

The Hausdorff metric between two non-empty
compact subsets of **R*** ^{n}* can be defined in the following
way.

·
If *B* is an element of *H*(**R*** ^{n}*), for each

*d*(*x*, *B*) = min{*d _{E}*(

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*(**R*** ^{n}*), define the distance

*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*(**R*** ^{n}*), the Hausdorff distance,

*h*(*A*, *B*) = max{*d*(*A*, *B*),
*d*(*B*, *A*)}.

The corresponding metric space, *H*(**R*** ^{n}*),
is then itself a complete metric space [1]. The applet here shows how