Introduced by Felix Hausdorff in the early 20th century as a way to measure the distance between sets, the Hausdorff metric (also called the Pompeiu-Hausdorff metric) has since been widely studied and has many applications. For example, the United States military has used the Hausdorff distance in target recognition procedures. In addition, the Hausdorff metric has been used in image matching and visual recognition by robots, medicine, image analysis, and astronomy.
The basic idea in these applications is that we need a way to compare two shapes. For example, if a manufacturer needs to mill a specific product based on a template, there is usually some tolerance that is allowed. So the manufacturer needs a way to compare the milled parts to the template to determine if the tolerance has been met or exceeded.
The Hausdorff metric is also familiar to fractal aficionados for describing the convergence of sequences of compact sets to their attractors in iterated function systems. The variety of applications of this metric make it one that is worth studying.
To define the Hausdorff metric, we begin with the distance from a point \(x\) in a metric space \(X\) to a subset \(A\) of \(X\) as
\begin{equation*}
d(x,A) = \inf\{d(x,a) \mid a \in A\}\text{.}
\end{equation*}
Since images will be represented as compact sets, we restrict ourselves to compact subsets of a metric space. In this case the infimum becomes a minimum and we have
\begin{equation*}
d(x,A) = \min\{d(x,a) \mid a \in A\}\text{.}
\end{equation*}
We now extend that idea to define the distance from one subset of \(X\) to another. Let \(A\) and \(B\) be nonempty compact subsets of \(X\text{.}\) To find the distance from the set \(A\) to the set \(B\text{,}\) it seems reasonable to consider how far each point in \(A\) is from the set \(B\text{.}\) Then the distance from \(A\) to \(B\) should measure how far we have to travel to get from any point in \(A\) to \(B\text{.}\)
Definition17.16.
Let \((X,d)\) be a metric space and let \(A\) and \(B\) be nonempty compact subsets of \(X\text{.}\) Then distance \(d(A,B)\) from \(A\) to \(B\) is
Note: since \(A\) and \(B\) are compact, \(d(A,B)\) is guaranteed to exist.
Activity17.8.
(a)
A problem with \(d\) as in Definition 17.16 is that \(d\) is not symmetric. Find examples of compact subsets \(A\) and \(B\) of \(\R^n\) with the Euclidean metric such that \(d(A,B) \neq d(B,A)\text{.}\)
(b)
Even though the function \(d\) in Definition 17.16 is not a metric, we can define the Hausdorff distance in terms of \(d\) as follows.
Definition17.17.
Let \((X,d)\) be a metric space and \(A\) and \(B\) nonempty compact subsets of \(X\text{.}\) Then Hausdorff distance between \(A\) and \(B\) is
Let \(A\) be the circle in \(\R^2\) centered at the origin with radius 1, let \(B\) be the inscribed square, and let \(C = \{(1,0), (-1,0)\}\) as shown in Figure 17.18.
Figure17.18.Sets \(A\text{,}\)\(B\text{,}\) and \(C\text{.}\)
Determine \(h(A,B)\text{,}\)\(h(A,C)\text{,}\) and \(h(B,C)\text{,}\) and verify that \(h(A,C) \leq h(A,B) + h(B,C)\text{.}\)
(c)
It may be surprising that \(h\) as in Definition 17.17 is actually a metric, but it is. The underlying space is the collection of nonempty compact subsets of \(X\) which we denote at \(\mathcal{H}(X)\text{.}\) Prove the following theorem.
Theorem17.19.
Let \(X\) be a metric space. The Hausdorff distance function is a metric on \(\mathcal{H}(X)\text{.}\)
(d)
One fun application of the Hausdorff metric is in fractal geometry. You may be familiar with objects like the Sierpinski triangle or the Koch curve. These objects are limits of sequences of sets in \(\mathcal{H}(\R^2)\text{.}\) We illustrate with the Sierpinski triangle. Start with three points \(v_1\text{,}\)\(v_2\text{,}\) and \(v_3\) that form the vertices of an equilateral triangle \(S_0\text{.}\) For \(i\)=1,2, or 3, let \(v_i = \begin{bmatrix}a_i \\ b_i \end{bmatrix}\text{.}\) For \(i\)=1,2, or 3, we define \(\omega_i : \R^2 \to \R^2\) by
Then \(\omega_i\text{,}\) when applied to \(S_0\text{,}\) contracts \(S_0\) by a factor of 2 and then translates the image of \(S_0\) so that the \(i^{\text{ th } }\) vertex of \(S_0\) and the \(i\)th vertex of the image of \(S_0\) coincide. Such a map is called a contraction mapping with contraction factor equal to \(\frac{1}{2}\text{.}\) Define \(S_{1,i}\) to be \(\omega_i(S_0)\text{.}\) Then \(S_{1,i}\) is the set of all points half way between any point in \(S_0\) and \(v_i\text{,}\) or \(S_{1,i}\) is a triangle half the size of the original translated to the \(i^{\text{ th } }\) vertex of the original. Let \(S_1 = \bigcup_{i=1}^3 S_{1,i}\text{.}\) Both \(S_0\) and \(S_1\) are shown in Figure 17.20. We can continue this procedure replacing \(S_0\) with \(S_1\text{.}\) In other words, for \(i\) = 1, 2, and 3, let \(S_{2,i} = \omega_i(S_1)\text{.}\) Then let \(S_2 = \bigcup_{i=1}^3 S_{2,i}\text{.}\) A picture of \(S_2\) is shown in Figure 17.20. We can continue this procedure, each time replacing \(S_{j-1}\) with \(S_j\text{.}\) A picture of \(S_8\) is shown in Figure 17.20.
\begin{equation*}
S_0
\end{equation*}
\begin{equation*}
S_1
\end{equation*}
\begin{equation*}
S_2
\end{equation*}
\begin{equation*}
S_8
\end{equation*}
Figure17.20.\(S_i\) for \(i\) equal to 0, 1, 2, and 8.
To continue this process, we need to take a limit. But the \(S_i\) are sets in \(\mathcal{H}(\R^2)\text{,}\) so the limit is taken with respect to the Hausdorff metric.
(i)
Assume that the length of a side of \(S_0\) is \(1\text{.}\) Determine \(h(S_0,S_1)\text{.}\) Then find \(h(S_k, S_{k+1})\) for an arbitrary positive integer \(k\text{.}\)
(ii)
The Sierpinski triangle will exist if the sequence \((S_n)\) converges to a set \(S\) (which would be the Sierpinski triangle). The question of convergence is not a trivial one.
(A)
Consider the sequence \((a_n)\text{,}\) where \(a_n = \left(1+\frac{1}{n}\right)^n\) for \(n \in \Z^+\text{.}\) Note that each \(a_n\) is a rational number. Explain why the terms in this sequence get arbitrarily close together, but the sequence does not converge in \(\Q\text{.}\) Explain why the sequence \((a_n)\) converges in \(\R\text{.}\)
(B)
A sequence \((x_n)\) in a metric space \((X,d)\) is a Cauchy sequence if given \(\epsilon \gt 0\) there exists \(N \in \Z^+\) such that \(d(x_n, x_m) \lt \epsilon\) whenever \(n, m \geq N\text{.}\) Every convergent sequence is a Cauchy sequence. A metric space \(X\) is said to be complete if every Cauchy sequence in \(X\) converges to an element in \(X\text{.}\) For example, \((\R, d_E)\) is complete while \((\Q, d_E)\) is not. Although we will not prove it, the metric space \((\mathcal{H}(\R^2), h)\) is complete. Show that the sequence \((S_n)\) is a Cauchy sequence in \(\mathcal{H}(\R^2)\text{.}\) The limit of this sequence is the famous Sierpinski triangle. The picture of \(S_8\) in Figure 17.20 is a close approximation of the Sierpinski triangle.
