# 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 *space*s (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,

*Hausdorff distance*r from each other iff any point of one set is within distance r from some point of the other set.

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

_{r}(A) = {y: d(x,y) < r for some x∈A}

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

_{r}(B) and B⊂N

_{r}(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:

- 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.
- 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

Any contraction f: Y → Y on a complete metric space Y has a unique *fixed point*.

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

_{1}, y

_{2}∈Y,

_{1}), f(y

_{2})) ≤ r*d(y

_{1}, y

_{2}),

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 _{k+1} = f(y_{k}).

## Convergence Theorem

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

## References

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

|Contact| |Front page| |Contents| |Up| |Geometry|

Copyright © 1996-2018 Alexander Bogomolny