Convergence of the Pythagorean Tree Iteration
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 $T_0$ be the initial square (shown in red in the figure below) and let $T_1$ be the first iteration (which adds the two gray squares to the initial red square). Let \(\alpha\) be the angle for the left square.
We want to determine the distance between $T_0$ and $T_1$. Since $T_0$ is a subset of $T_1$, then $T_0$ is also a subset of the $r$-envelope of $T_1$ for all values of $r$. Therefore we only need to look at the values of $r$ for which $T_1$ is a subset of the $r$-envelope of $T_0$.
From this drawing we can see that the critical value of $r$ is at most the length of the diagonal of the larger square that is added to $T_0$ to construct $T_1$. Let's assume that each side of $T_0$ has length 1. Then the sides of the two gray squares in $T_1$ have lengths \(\cos(\alpha)\) and \(\sin(\alpha)\). Let $w$ be the larger of these lengths. Then
\[D \left( {T_0,T_1} \right) \leq \sqrt 2 \cdot w\]What about the distance between $T_1$ and $T_2$? Here we have the following situation
where the gray squares are added to $T_1$ (red region) to form $T_2$. As before, the critical value of $r$ is at most the length of the diagonal of the largest gray square. The side of this gray square has length \({w^2}\) and therefore
\[D\left( {T_1,T_2} \right) \leq \sqrt 2 {w^2}\]
Now the same idea can also be used to compute the distance between $T_k$ and $T_{k+1}$. This will be determined by the length of the diagonal of the largest square that is added to $T_k$ to get $T_{k+1}$. The side of the largest square has length \({w^{k+1}}\). Therefore
\[D\left( T_k,T_{k+1} \right) \leq \sqrt 2 {w^{k+1}}\]
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 $T_n$ and $T_m$ for $m \gt n$. But this is easy because the terms for the distance between consecutive sets are part of a geometric sequence with \(w \lt 1\).
\[\begin{aligned} D\left( {T_n,T_m)} \right) &\le \sum\limits_{k = n}^{m - 1} {D\left( {T_k,T_{k+1}} \right)} \le \sum\limits_{k = n}^\infty {D\left( {T_k,T_{k+1}} \right)} \\ &\le \sum\limits_{k = n}^\infty {\sqrt 2 {w^{k + 1}}} = \frac{{\sqrt 2 {w^{n + 1}}}}{{1 - w}} \\ \end{aligned} \]
(The first inequality follows from using the triangle inequality for the Hausdorff metric.) Given a value for $\varepsilon$, all we need to do is pick $N$ so that
\[\frac{{\sqrt 2 {w^{N + 1}}}}{{1 - w}} \lt \varepsilon \]
and then $D\left( {T_n,T_m)} \right) \lt \varepsilon$ for all $n,m \gt N$. This shows that the sequence of sets is a Cauchy sequence in the Hausdorff metric and that the sets therefore converge to a limit.
