Classic Iterated Function Systems

Convergence of the Koch Construction

The Hausdorff distance for compact sets

For two non-empty compact subsets \( A, B \subset \mathbb{R}^2 \), the Hausdorff distance is defined as \[ D(A, B) = \max \left\{ \sup_{a \in A} \inf_{b \in B} d(a, b), \sup_{b \in B} \inf_{a \in A} d(b, a) \right\} \] where \(d(a,b)\) is the usual Euclidean distance between the points \(a\) and \(b\). Here \(\displaystyle \inf_{b \in B} d(a, b)\) is the shortest distance of \(a\) to all of the points in \(B\). Now do the same in the other direction and then take the maximum of both to get the Hausdorff distance of set \(A\) from set \(B\). This can be summarized as the maximum of the distances from any point in $A$ to the nearest point in $B$, and the distances from any point in $B$ to the nearest point in $A$. This is a metric on the space of all non-empty compact sets in the plane, so it satisfies all the usual properties of a distance function. It makes the space of non-empty compact subsets a complete metric space.

The Koch construction converges to a limit

Let (\(P_n\)) be the sequence of polygonal lines from the iterative construction of the Koch curve with \(P_0\) being the initial line segment. Here are the first three iterations.

We will prove that this sequence of polygonal lines is a Cauchy sequence. Let us first find the distance between \(P_0\) and \(P_1\). We can take \(P_0\) to be of unit length. Here we show the two sets together in the plane.

The drawing below shows that the midpoint of \(P_0\) is the point in \(P_0\) that is farthest from \(P_1\). This distance is \(\frac{1}{6}\sin(60^\circ)=\frac{\sqrt{3}}{12}\).

And this next drawing shows that the top of the equilateral triangle is the point in \(P_1\) that is farthest from \(P_0\). This distance is the height of the equilateral triangle. Since the base of the equilateral triangle is 1/3, the height of the triangle is \( \frac{1}{3}\cdot\frac{\sqrt{3}}{2}\).

Therefore \[D(P_0,P_1) = \max \left \{\frac{\sqrt{3}}{12}, \frac{\sqrt{3}}{6}\right\} = \frac{\sqrt{3}}{6}.\]

What about the distance between \(P_1\) and \(P_2\)? Here we have the following situation.

The set \(P_2\) consist of four copies of \(P_1\) scaled by 1/3. By the same reasoning as above, the distance between the two sets is the height of the four equilateral triangles. These heights have also been scaled by 1/3, and so \[D(P_1,P_2)=\frac{\sqrt{3}}{6}\left(\frac{1}{3}\right).\]

Each subsequent iteration will scale the heights of the equilateral triangles by another factor of 1/3. We can therefore conclude that \[D(P_n,P_{n+1})=\frac{\sqrt{3}}{6}\left(\frac{1}{3}\right)^n.\]

We 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 \(P_n\) and \(P_m\) for \(m > n\). But this is easy because the terms for the distance between consecutive sets make up a geometric sequence.

\[ D\left( {P_n,P_m} \right) \le \sum\limits_{k = n}^{m - 1} D(P_k,P_{k+1}) \le \sum\limits_{k = n}^\infty D(P_k,P_{k+1}) = \sum\limits_{k = n}^\infty \frac{\sqrt{3}}{6}\left(\frac{1}{3}\right)^k = \frac{\frac{\sqrt{3}}{6}\left(\frac{1}{3}\right)^n} {1-\frac{1}{3}} = \frac{\sqrt{3}}{4}\left(\frac{1}{3}\right)^n \]

(The first inequality follows from using the triangle inequality for the Hausdorff metric.) Given a value for \(\varepsilon\ \gt 0\), all we need to do is pick \(N\) so that \[\frac{\sqrt{3}}{4}\left(\frac{1}{3}\right)^n \lt \varepsilon\] and then \(D\left( {P_n,P_m} \right) \lt \varepsilon\) for all \(n,m > N\). This shows that the sequence of polygonal lines is a Cauchy sequence and that therefore the sequence converges to a limit. This limit is the Koch curve \(K\).

Since each polygonal line \(P_n\) is connected and compact, and \(\displaystyle \lim_{n \rightarrow \infty}P_n=K\) in the Hausdorff metric, the Koch curve is also connected and compact. Since \(K\) is connected and the fixed set (attractor) of an iterated function system, it is a curve by Theorem 6.5 in reference (1).

Note: Convergence via Banach Fixed Point Theorem

Hutchinson's Theorem can also be used to show the convergence of the Koch construction of polygonal lines. The following iterated function system consists of four contractive maps.

If the Hutchinson operator \(F\) is given by \(F(A) = f_1(A) \cup f_2(A) \cup f_3(A) \cup f_4(A)\) for a non-empty compact set \(A\) in the plane, then \(F\) is a contractive map by Hutchinson's Theorem. Since

\[P_1 = F(P_0), \,P_2 = F(P_1),\, P_3 = F(P_2), \,\dots, P_n = F(P_{n-1}), \,\dots\]

and \(F\) is a contraction on a complete metric space, the Banach Fixed Point Theorem guarantees that

1. there exists a unique fixed point \(A^*\) such that \(\displaystyle A^* = F(A^*) = \bigcup_{n=1}^4 f_n(A^*)\);
2. the sequence of polygonal lines \(P_n = F(P_{n-1})\) converges to \(A^*\) in the Hausdorff metric.

So the Koch construction converges to the IFS fixed point (attractor). But by definition, the Koch curve is the limit of the polygonal lines \(P_n\) in the Koch construction. Therefore the attractor of the iterated function system must be the Koch curve. The Banach Fixed Point theorem also guarantees that the sequence \(A_n = F(A_{n-1})\) converges to the attractor of the IFS, i.e. the Koch curve, for \(\textit{any}\) initial non-empty compact set \(A_0\).