27.1
Iterated Function Systems and Fractals
A pleasant application of the Hausdorff distance and of the fixed point theorem for contract-
ing mappings is a method for defining a class of “self-similar” fractals. For this, we can use
iterated function systems.
Definition 27.1. Given a metric space, (X, d), an iterated function system, for short, an
ifs, is a finite sequence of functions, (f1, . . . , fn), where each fi : X → X is a contracting
mapping. A nonempty compact subset, K, of X is an invariant set (or attractor) for the ifs,
(f1, . . . , fn), if
K = f1(K) ∪ · · · ∪ fn(K).
The major result about ifs’s is the following:
Theorem 27.1. If (X, d) is a nonempty complete metric space, then every iterated function
system, (f1, . . . , fn), has a unique invariant set, A, which is a nonempty compact subset of
X. Furthermore, for every nonempty compact subset, A0, of X, this invariant set, A, if the
limit of the sequence, (Am), where Am+1 = f1(Am) ∪ · · · ∪ fn(Am).
Proof. Since X is complete, by Theorem 26.39, the space (K(X), D) is a complete metric
space. The theorem will follow from Theorem 26.38 if we can show that the map,
F : K(X) → K(X), defined such that
F (K) = f1(K) ∪ · · · ∪ fn(K),
for every nonempty compact set, K, is a contracting mapping. Let A, B be any two nonempty
compact subsets of X and consider any η ≥ D(A, B). Since each fi : X → X is a contracting
mapping, there is some λi, with 0 ≤ λi < 1, such that
d(fi(a), fi(b)) ≤ λid(a, b),
773
774
CHAPTER 27. A DETOUR ON FRACTALS
for all a, b ∈ X. Let λ = max{λ1, . . . , λn}. We claim that
D(F (A), F (B)) ≤ λD(A, B).
For any x ∈ F (A) = f1(A) ∪ · · · ∪ fn(A), there is some ai ∈ Ai such that x = fi(ai) and since
η ≥ D(A, B), there is some bi ∈ B such that
d(ai, bi) ≤ η,
and thus,
d(x, fi(bi)) = d(fi(ai), fi(bi)) ≤ λid(ai, bi) ≤ λη.
This show that
F (A) ⊆ Vλη(F (B)).
Similarly, we can prove that
F (B) ⊆ Vλη(F (A)),
and since this holds for all η ≥ D(A, B), we proved that
D(F (A), F (B)) ≤ λD(A, B)
where λ = max{λ1, . . . , λn}. Since 0 ≤ λi < 1, we have 0 ≤ λ < 1 and F is indeed a
contracting mapping.
Theorem 27.1 justifies the existence of many familiar “self-similar” fractals. One of the
best known fractals is the Sierpinski gasket.
Example 27.1. Consider an equilateral triangle with vertices a, b, c, and let f1, f2, f3 be
the dilatations of centers a, b, c and ratio 1/2. The Sierpinski gasket is the invariant set of
the ifs (f1, f2, f3). The dilations f1, f2, f3 can be defined explicitly as follows, assuming that
√
a = (−1/2, 0), b = (1/2, 0), and c = (0, 3/2). The contractions f1, f2, f3 are specified by
1
1
x
=
x − ,
2
4
1
y
=
y,
2
1
1
x
=
x + ,
2
4
1
y
=
y,
2
and
1
x
=
x,
2
√
1
3
y
=
y +
.
2
4
27.1. ITERATED FUNCTION SYSTEMS AND FRACTALS
775
Figure 27.1: The Sierpinski gasket
We wrote a Mathematica program that iterates any finite number of affine maps on any
input figure consisting of combinations of points, line segments, and polygons (with their
interior points). Starting with the edges of the triangle a, b, c, after 6 iterations, we get the
picture shown in Figure 27.1.
It is amusing that the same fractal is obtained no matter what the initial nonempty
compact figure is. It is interesting to see what happens if we start with a solid triangle (with
its interior points). The result after 6 iterations is shown in Figure 27.2. The convergence
towards the Sierpinski gasket is very fast. Incidently, there are many other ways of defining
the Sierpinski gasket.
A nice variation on the theme of the Sierpinski gasket is the Sierpinski dragon.
Example 27.2. The Sierpinski dragon is specified by the following three contractions:
√
1
3
3
x
= − x −
y + ,
4
4
4
√
√
3
1
3
y
=
x − y +
,
4
4
4
√
1
3
3
x
= − x +
y − ,
4
4
4
√
√
3
1
3
y
= −
x − y +
,
4
4
4
1
x
=
x,
2
√
1
3
y
=
y +
.
2
2
776
CHAPTER 27. A DETOUR ON FRACTALS
Figure 27.2: The Sierpinski gasket, version 2
The result of 7 iterations starting from the line segment (−1, 0), (1, 0)), is shown in Figure
27.3. This curve converges to the boundary of the Sierpinski gasket.
A different kind of fractal is the Heighway dragon.
Example 27.3. The Heighway dragon is specified by the following two contractions:
1
1
x
=
x − y,
2
2
1
1
y
=
x + y,
2
2
1
1
x
= − x − y,
2
2
1
1
y
=
x − y + 1.
2
2
It can be shown that for any number of iterations, the polygon does not cross itself. This
means that no edge is traversed twice and that if a point is traversed twice, then this point
is the endpoint of some edge. The result of 13 iterations, starting with the line segment
((0, 0), (0, 1)), is shown in Figure 27.4.
The Heighway dragon turns out to fill a closed and bounded set. It can also be shown
that the plane can be tiled with copies of the Heighway dragon.
Another well known example is the Koch curve.
27.1. ITERATED FUNCTION SYSTEMS AND FRACTALS
777
Figure 27.3: The Sierpinski dragon
Figure 27.4: The Heighway dragon
778
CHAPTER 27. A DETOUR ON FRACTALS
Figure 27.5: The Koch curve
Example 27.4. The Koch curve is specified by the following four contractions:
1
2
x
=
x − ,
3
3
1
y
=
y,
3
√
1
3
1
x
=
x −
y − ,
6
6
6
√
√
3
1
3
y
=
x + y +
,
6
6
6
√
1
3
1
x
=
x +
y + ,
6
6
6
√
√
3
1
3
y
= −
x + y +
,
6
6
6
1
2
x
=
x + ,
3
3
1
y
=
y.
3
The Koch curve is an example of a continuous curve which is nowhere differentiable
(because it “wiggles” too much). It is a curve of infinite length. The result of 6 iterations,
starting with the line segment ((−1, 0), (1, 0)), is shown in Figure 27.5.
The curve obtained by putting three Kock curves together on the sides of an equilateral
triangle is known as the snowflake curve (for obvious reasons, see below!).
27.1. ITERATED FUNCTION SYSTEMS AND FRACTALS
779
Figure 27.6: The snowflake curve
Example 27.5. The snowflake curve obtained after 5 iterations is shown in Figure 27.6.
The snowflake curve is an example of a closed curve of infinite length bounding a finite
area.
We conclude with another famous example, a variant of the Hilbert curve.
Example 27.6. This version of the Hilbert curve is defined by the following four contrac-
tions:
1
1
x
=
x − ,
2
2
1
y
=
y + 1,
2
1
1
x
=
x + ,
2
2
1
y
=
y + 1,
2
1
x
= − y + 1,
2
1
1
y
=
x + ,
2
2
1
x
=
y − 1,
2 1 1
y
= − x + .
2
2
780
CHAPTER 27. A DETOUR ON FRACTALS
Figure 27.7: A Hilbert curve
This continuous curve is a space-filling curve, in the sense that its image is the entire
unit square. The result of 6 iterations, starting with the two lines segments ((−1, 0), (0, 1))
and ((0, 1), (1, 0)), is shown in Figure 27.7.
For more on iterated function systems and fractals, we recommend Edgar [31].