Larry Riddle, Agnes Scott College

The Hausdorff distance between two compact sets
**A** and **B** is given by

\[D(A,B) = \inf \left\{ {r:A \subseteq {N_r}(B) \text{ and } B \subseteq {N_r}(A)} \right\}\]

where for a set **W**, N_{r}(**W**) is the **r**-envelope of **W**; that
is, the set of all points that are within a distance **r** of some
point in **W**.

Let's first determine the distance between **S(0)** and the first
iteration **S(1)**.

Since **S(0)** is a subset of **S(1)**, then **S(0)** is also a
subset of the **r**-envelope of **S(1)** for all values of
**r**. Therefore we only need to look at the values of **r**
for which **S(1)** is a subset of the **r**-envelope of
**S(0)**.

From this drawing we can see that the critical value of **r**
is the height of the small equilateral triangles that are added to
**S(0)** to construct **S(1)**. The height of an equilateral
triangle with side length **a** can be found using the Pythagorean
Theorem as illustrated in this figure

Let's assume that each side of **S(0)** has length 1. Then
**a** = 1/3 is the length of the red triangles that we add to
**S(0)** to get **S(1)**. From our result with the Pythagorean
Theorem, therefore, we know that

\[D\left( {S(0),S(1)} \right) = \frac{1}{3} \cdot \frac{{\sqrt 3 }}{2}\]

What about the distance between **S(1)** and **S(2)**? Here
we have the following situation

and we can see that for the same reason as before, the distance
will be the height of the red triangles that are added to **S(1)**
to get **S(2)**. Here **a** = 1/9, so

\[D\left( {S(1),S(2)} \right) = \frac{1}{{{3^2}}} \cdot \frac{{\sqrt 3 }}{2}\]

Now the same idea can also be used to compute the distance between
**S(k)** and **S(k+1)**. This will be the same as the height of
the new triangles that are added to **S(k)** to get **S(k+1)**
as we see in this diagram.

Each side of **S(k)** has length (1/3)^**k**, and so the
length of the new equilateral triangles for **S(k+1)** is
**a**=(1/3)^(**k**+1). Therefore

\[D\left( {S(k),S(k + 1)} \right) = \frac{1}{{{3^{k + 1}}}} \cdot \frac{{\sqrt 3 }}{2}\]

We actually want to show that the sequence of sets is a Cauchy
sequence in the Hausdorff metric, so we need to get an estimate for
the distance between **S(n)** and **S(m)** for **m **>
**n**. But this is easy because the terms for the distance between
consecutive sets make up a geometric sequence:

\[\begin{align} D\left( {S(n),S(m)} \right) &\le \sum\limits_{k = n}^{m - 1} {D\left( {S(k),S(k + 1)} \right)} \le \sum\limits_{k = n}^\infty {D\left( {S(k),S(k + 1)} \right)} \\ \\ &= \sum\limits_{k = n}^\infty {\frac{1}{{{3^{k + 1}}}} \cdot \frac{{\sqrt 3 }}{2}} = \frac{{\frac{1}{{{3^{n + 1}}}} \cdot \frac{{\sqrt 3 }}{2}}}{{1 - \frac{1}{3}}} = \frac{1}{{{3^n}}} \cdot \frac{{\sqrt 3 }}{4} \\ \end{align}\]

(The first inequality follows from using the triangle inequality
for the Hausdorff metric.) Given a value for ε, all we need to
do is pick **N** so that

\[\frac{1}{{{3^N}}} \cdot \frac{{\sqrt 3 }}{4} < \varepsilon \]

and then D(**S(n)**, **S(m)**) < ε for all
**n**, **m** > **N**. This shows that the sequence of
sets is a Cauchy sequence and that the sets therefore converge to a
limit.