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, Nr(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.
