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.