Classic Iterated Function Systems

Koch Curve

"It is this similarity between the whole and its parts, even infinitesimal ones, which leads us to consider the von Koch curve as a truly spectacular line among all. If it were endowed with life, it would be impossible to annihilate it without eliminating it from the outset, because it would constantly resurface from the depths of its triangles, like life in the Universe!"

E. Cesàro, Atti d. R. Accademia d. Scienze d. Napoli, 2, XII, number 15.

Begin with a straight line (the blue segment in the top figure). Divide it into three equal segments and replace the middle segment by the two sides of an equilateral triangle of the same length as the segment being removed (the two red segments in the middle figure). Now repeat, taking each of the four resulting segments, dividing them into three equal parts and replacing each of the middle segments by two sides of an equilateral triangle (the red segments in the bottom figure). Continue this construction.

The Koch curve, described by Helge von Koch in a 1904 paper, is the limiting curve obtained by applying this construction of polygonal lines an infinite number of times. For an analytic proof that this construction does produce a "limit" that is an actual curve, i.e. the continuous image of the unit interval, see the texts by Darst et al. [4, section 2.1.3] or Edgar [5, proposition 2.3.10], or Koch's original proof given in Edgar [6, Chapter 3]. The limit can also be established using the Hausdorff metric on the space of non-empty compact sets in the plane [Convergence Details].

In 1905, the Italian mathematician, Ernesto Cesàro, described an alternative construction of the Koch curve using isosceles triangles. He also recognized that the Koch curve is self-similar and used that to explain some of the properties of the curve found by Koch. [Cesàro Details]

The first iteration for the Koch curve consists of taking four copies of the unit horizontal line segment, each scaled by $r$ = 1/3. Two segments must be rotated by 60°, one counterclockwise and one clockwise.
 

Along with the required translations, this yields the following IFS.
 

The fixed attractor of this IFS is the Koch curve.

Here is an iterated function system based on the 1906 construction by Ernesto Cesàro using isosceles triangles [Cesàro Details].

Angle 60
Axiom F
F —> F+F−−F+F

The Koch curve is self-similar with 4 non-overlapping copies of itself, each scaled by the factor $r \lt 1$. Therefore the similarity dimension, $d$, of the attractor of the IFS is the solution to

\[\sum\limits_{k = 1}^4 {{r^d}} = 1 \quad \Rightarrow \quad d = \frac{{\log (1/4)}}{{\log (1/3 )}} = \frac{{\log (4)}}{{\log (3 )}} = 1.26186 \]

Koch constructed his curve in 1904 as an example of a non-differentiable curve, that is, a continuous curve that does not have a tangent at any of its points [Video]. Karl Weierstrass had first demonstrated the existence of such a curve in 1872. Here are Koch's drawings from his 1904 (and 1906) paper illustrating a combination of the first four iterations (what he called polygonal lines) in his construction of the curve.

The length of the intermediate curve at the nth iteration of the construction is $(4/3)^n$, where $n=0$ denotes the original straight line segment. Therefore the length of the Koch curve is infinite. Moreover, as noted by Koch in his original article, the length of the arc between any two points on the curve is infinite since there is a copy of the Koch curve between any two points. Cesàro gave an alternative proof using the self-similarity of the Koch curve.

One of the other observations addressed in Koch's original paper was to evaluate the area contained between the curve and the initial horizontal chord of length 1, which Koch showed was \(\displaystyle \frac{1}{20}\sqrt{3}\) using the sum of a geometric series. This result can also be obtained by exploiting the self-similarity of the Koch curve [Area Details].

Three copies of the Koch curve placed outward around the three sides of an equilateral triangle form a simple closed curve that forms the boundary of the Koch snowflake. Three copes of the Koch curve placed so that they point inside the equilateral triangle create a simple closed curve that forms the boundary of the Koch anti-snowflake. Use the buttons below to toggle between the two options.

For a second variation, let $K = \{f_1, f_2, f_3, f_4\}$ be the four functions in the Koch IFS. Let $G$ be either the cyclic symmetry group $Z_n$ or the dihedral symmetry group $D_n$ for ${n \ge 2}$. The group $Z_n$ consists of counterclockwise rotations through angles that are multiples of 360°/$n$. The group $D_n$ consists of symmetries of a regular polygon with $n$ sides, including both the same rotations as in $Z_n$ and also reflections. The one exception is $D_2$ since there is no regular polygon with 2 sides. This group $D_2$ is also known as the Klein four-group.

We can form a new IFS by applying each of the symmetries in $G$ to each of the functions in $K$, i.e. form the set of affine transformations $GK = \{ gf : g \in G \text{ and } f \in K\}$. For example, if $G = Z_3$, then the three elements of $G$ are the identity (no rotation), $r_{120}$, a counterclockwise rotation through 120°, and $r_{240}$, a counterclockwise rotation through 240°. The new IFS would then consist of the 12 functions $\{f_k, r_{120}f_k, r_{240}f_k \text{ for } k = 1,2,3,4\}$. The first iteration would look like the following (using a horizontal line as the initial set as in the construction of the regular Koch curve).

This IFS again has a unique attractor, shown below, since each of the 12 affine transformations is contractive.

Notice that the self-similar parts of this fractal overlap, but that overall the fractal has three-fold rotational symmetry. If we rotate the fractal by 120°, then we are really just applying $r_{120}$ to each of the 12 functions in the IFS. But this just permutes the elements of the IFS. For example, $r_{120}r_{120}f_k$ is just the same as $r_{240}f_k$ since two rotations through 120° is the same as one rotation through 240°. So if $A$ is the attractor for the IFS, then \[A = \bigcup\limits_{k = 1}^4 {\left( {{f_k}(A)\cup {{r_{120}}{f_k}(A)\cup {{r_{240}}{f_k}(A)} } } \right)} \] and rotating $A$ by 120° yields \[\begin{align} {r_{120}}(A) &= {r_{120}}\left( {\bigcup\limits_{k = 1}^4 {\left( {{f_k}(A)\cup {{r_{120}}{f_k}(A)\cup {{r_{240}}{f_k}(A)} } } \right)} } \right) \\ &= \bigcup\limits_{k = 1}^4 {\left( {{r_{120}}{f_k}(A)\cup {{r_{240}}{f_k}(A)\cup {{f_k}(A)} } } \right)} = A \\ \end{align}\]

The four elements of the group $Z_4$ produces rotational symmetry with angles of 0°, 90°, 180°, and 270°. Applying these to the Koch curve iterated system produces the following fractal with four-fold rotational symmetry. It is colored using pixel counting (the color depends on how many times a particular pixel is plotted during the drawing of the fractal using the random chaos game algorithm).

Here is the fractal obtained using the dihedral group $D_4$. It is also colored using pixel counting. This fractal has both four-fold rotational symmetry (through rotations of 90°) as well as a reflective symmetry across horizontal, vertical, and diagonal lines. Click for more details on symmetric fractals or see the book by Field and Golubitsky.

[Enlarge]