Classic Iterated Function Systems

Convergence of the Sierpinski Gasket 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 Sierpinski gasket construction converges to a limit

Let (\(S_n\)) be the sequence obtained from the iterative construction of the Sierpinski gasket with \(S_0\) being the initial equilateral triangle shown in green. Here are the first two iterations, \(S_1\) and \(S_2\).

     

We will prove that this sequence is a Cauchy sequence in the Hausdorff metric. Let us first find the distance between \(S_0\) and \(S_1\). Here we show the two sets together in the plane with \(S_1\) on top. The green triangle is the part of \(S_0\) that is visible once the middle triangle is removed in the construction to obtain \(S_1\).

Since \(S_1\) is a subset of \(S_0\), the distance from each point in \(S_1\) to the set \(S_0\) is 0. Therefore \(\displaystyle \sup_{y \in S_1} \inf_{x \in S_0} d(y,x)=0.\) The drawing above shows that the centroid (yellow dot) of the green equilateral triangle is the point in \(S_0\) that is farthest from \(S_1\). This distance is \(\frac{1}{2}\tan(30^\circ)=\frac{\sqrt{3}}{6}\). Therefore \[D(S_0,S_1) = \max \left \{0, \frac{\sqrt{3}}{6}\right\} = \frac{\sqrt{3}}{6}.\]

What about the distance between \(S_1\) and \(S_2\)? Again we show the two sets together in the plane with \(S_2\) on top and the red triangles being the parts of \(S_1\) that become visible during the construction of \(S_2\).

The drawing shows that the centroids (yellow dots) of the red equilateral triangles are the points in \(S_1\) that are farthest from \(S_2\). Since the triangles are scaled by 1/2 at each iteration of the construction, the distance to the centroids is also scaled by 1/2. Therefore \[D(S_1,S_2) = \max \left \{0, \frac{\sqrt{3}}{6}\cdot\frac{1}{2}\right\} = \frac{\sqrt{3}}{6}\cdot\frac{1}{2}.\]

Each subsequent iteration will scale the equilateral triangles by another factor of 1/2. We can therefore conclude that \[D(S_n,S_{n+1})=\frac{\sqrt{3}}{6}\left(\frac{1}{2}\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 \(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.

\[ D\left( {S_n,S_m} \right) \le \sum\limits_{k = n}^{m - 1} D(S_k,S_{k+1}) \le \sum\limits_{k = n}^\infty D(S_k,S_{k+1}) = \sum\limits_{k = n}^\infty \frac{\sqrt{3}}{6}\left(\frac{1}{2}\right)^k = \frac{\frac{\sqrt{3}}{6}\left(\frac{1}{2}\right)^n} {1-\frac{1}{2}} = \frac{\sqrt{3}}{3}\left(\frac{1}{2}\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}}{3}\left(\frac{1}{2}\right)^n \lt \varepsilon\] and then \(D\left( {S_n,S_m} \right) \lt \varepsilon\) for all \(n,m > N\). This shows that the sequence (S_n) is a Cauchy sequence and that therefore the sequence converges to a limit. This limit is the Sierpinski gasket \(SG\).

Because the sequence (\(S_n\)) is a decreasing sequence of compact sets, \[\displaystyle SG = \lim_{n \rightarrow \infty}S_n =\bigcap_{n=0}^\infty S_n.\] And since each set \(S_n\) is connected and compact, the Sierpinski triangle is also connected and compact. In particular, since \(SG\) is connected and the fixed set (attractor) of an iterated function system (see below), 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 Sierpinski gasket construction. The following iterated function system consists of three contractive maps.

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

\[S_1 = F(S_0), \,S_2 = F(S_1),\, S_3 = F(S_2), \,\dots, S_n = F(S_{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}^3 f_n(A^*)\);
2. the sequence of sets \(S_n = F(S_{n-1})\) converges to \(A^*\) in the Hausdorff metric.

So the Sierpinski construction converges to the IFS fixed point (attractor). But by definition, the Sierpinski gasket is the limit of the sets \(S_n\) in the Sierpinski construction. Therefore the attractor of the iterated function system must be the Sierpinski gasket. 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 Sierpinski gasket, for \(\textit{any}\) initial non-empty compact set \(A_0\).