Hausdorff Distance

We talk about points in a space, like in the definition of a circle as a set of all points equidistant from a given point. But we have already pointed to an example of a distance defined between two functions. Functions can also be added and multiplied, and in mathematics sets whose elements are functions are called spaces (sometimes, of course, functional spaces.) as many other sets. The advantage is in that, once some common properties of various sets have been isolated, their study will apply to all the particular cases regardless of the nature of elements the sets comprise. It may be confusing sometimes, for example, when we consider spaces of functions or curves or matrices. A point in a space is something elementary, simple and, like an atom (of many years ago), indivisible. But here exactly lies one of the sources from which mathematics draws its power. Going to a level of abstraction that knows nothing of the nature of the objects it deals with spreads the results over vast territory strewn with apparently unrelated objects pointing to unexpected similarities and, by doing so, outlines also the limits of analogy. We not only learn what is common but better understand the differences.

Here I wish to consider spaces whose elements - points - are sets themselves. Proving a result on separating points in the plane with circles Richard Beigel considered the space of all circles with centers in a bounded region and bounded radii and used its compactness property. We also know that sets can be added and multiplied. So, it may not come as a surprise, after all, that there is a way to define and, therefore, measure distance between two sets.

Addition of sets was based on our ability to add their elements. Felix Hausdorff (1868 -1942) devised a metric function between subsets of a metric space. By definition,

More formally, let there be a space X with a metric function d. For every AX, and r > 0, we define an open neighborhood as

Nr(A) = {y: d(x,y) < r for some xA}

The Hausdorff metric h(A,B) is defined in terms of the neighborhoods. For any two subsets A and B of X,

h(A,B) = inf{r: ANr(B) and BNr(A)},

where inf(R) is the Greatest Lower Bound of a set R (compare to the Lowest Upper Bound.) To avoid unnecessary pitfalls we shall restrict our attention to a special kind of sets. To see why, consider the following examples:

1. h((0,1),[0,1]) = 0 although two sets (0,1) and [0,1] are different. This contradicts the first metric axiom. If both A and B are closed h(A,B) = 0 implies A = B. So, in the following, we shall only consider closed sets.
2. h({0}, [0,)) is so to have h finite we shall only consider bounded sets.

On a line or plane and, in general, in a finite dimensional space, sets that are both bounded and closed have the property of (sequential) compactness (Bolzano-Weierstrass Theorem):

On more general spaces Hausdorff metric is usually considered on the space of compact subsets K(X). We are interested in the Hausdorff metric because of the following two theorems:

Completeness Theorem

If X is complete, so is K(X).

Contraction Mapping Theorem

I'll later explain with examples the utility of the two theorems and of the general framework offered by the metrization of families of sets for construction of fractals with the Iteration Function Systems. Here I only want to add a few words on the terminology used in the Contraction Mapping theorem. A mapping f is a contraction iff

for any two points y1, y2Y, d(f(y1),f(y2))r*d(y1,y2), for some positive constant r < 1.

Contraction mappings reduce distance between points. For any such mapping on a complete space there exists a unique fixed point, i.e., a point y that remains unmoved by f: y = f(y). Such points may be approached by iterations y_k+1 = f(y_k). Moreover, the following theorem holds

Convergence Theorem

Let f be a contraction mapping of a complete space Y into itself. Choose arbitrary point y₀Y and form a sequence y_k+1 = f(y_k), k = 0,1,2,... Then the sequence {y_k} converges to the fixed point y of the mapping f.

References

1. M.Barnsley, Fractals Everywhere, Academic Press, 1988
2. G. A. Edgar, Measure, Topology, and Fractal Geometry, Springer UTM, 1995 (third printing)