FRACTALS AS FIXED POINTS OF ITERATED FUNCTION SYSTEMSCHRISTOPHER NATOLI

Abstract. This paper discusses one method of producing fractals, namely that of
iterated function systems. We first establish the tools of Hausdorff measure and Hausdorff dimension to analyze fractals, as well as some concepts in the theory of metricspaces. The latter allows us to prove the existence and uniqueness of fractals as fixed
points of iterated function systems. We discuss the connection between Hausdorff dimension and iterated function systems, and then study an application of fractals as
unique fixed points in dynamical systems theory.

Contents
Introduction
1. Hausdorff measure
2. Metric spaces
3. Iterated function systems
4. Fractals in dynamical systems
Acknowledgments
References
Appendix

1
2
7
9
14
17
17
17

Introduction
Geometry is often concerned with smooth or regular sets and functions. Much can besaid, however, about those sets that are not smooth or regular. Moreover, such objects canbetter represent many natural phenomena. We turn to fractal geometry as one means ofilluminating non-smooth and irregular objects.
Fractals are sets that satisfy most if not all of the following properties:• The set has a fine, intricate structure, with detail at arbitrarily small scales.
• It is too irregular to be described with classical geometry. Nonetheless, it has asimple, possibly recursive definition.
• It possesses some form of self-similarity, that is, it is composed of scaled copies ofitself.
• Its dimension exceeds what we would intuitively think of as its dimension. Often
its dimension is between integers. (We will explain this more rigorously later.)Consider the Cantor set as an example of a fractal. Start
 with the segment [0, 1] andremove the middle third, leaving you with segments 0, 31 and 23 , 1 . Then remove theDate: 26 August 2012.
1

2

CHRISTOPHER NATOLI

middle third from each of those segment. Repeat this procedure indefinitely. The resulting
object is called the Cantor set. See Figure 1 for a few iterations toward the Cantor set.

Figure 1. A few iterations toward the Cantor set, from [9].
Note how the Cantor set satisfies the conditions above to be a fractal. It is simply
defined: it is constructed by just recursively removing the middle third of every segment.
This definition gives rise to its self-similarity; a small section of the Cantor set is just a
scaled version of the entire set. Indeed, this gives it fine structure at small scales. If you
keep “zooming in” to the Cantor set, what you see is small versions of itself, with detailno matter how small the scale. Its dimension, as we will rigorously define in Section 1 and2then compute, is log
log 3 .
To better study fractals, we will need some tools from measure theory. In particular,
we will use the Hausdorff measure, which begets the concept of Hausdorff dimension, tobetter understand the size of fractals. This will allow us to study fractals produced by one
particular method, namely, iterated function systems. For every iterated function system,
there exists a unique fixed point, which is a fractal. Proving this fact is a key part ofthis paper. To do so, we will need some tools in the theory of metric spaces, which we will
establish before proving this theorem. We will then discuss how this theorem yields fractals
and allows us to easily compute their dimension. We will also look into an application ofthis theorem and fractals in general to the theory of dynamical systems.
1. Hausdorff measure
Before we begin to analyze fractals, we must first introduce some concepts in measure
theory. These tools will prove useful for studying the exotic nature of fractals. We willneed to use a measure other than the usual Lebesgue measure. We recall the Lebesgue
measure here:
Definition 1.1. Let {Bi } be a countable collection of n-dimensional boxes, i.e., subsets
of Rn such that Bi = {(x1 , . . . , xn ) ∈ Rn : aj ≤ xj ≤ bj for aj < bj and j = 1, . . . , n} . We
will write the n-dimensional volume of Bi as vol(Bi ) = (b1 − a1 )(b2 − a2 ) · · · (bn − an ).
Then the Lebesgue measure of a subset E of Rn is
(
)
X
[
n
L (E) = inf
vol(Bi ) : E ⊂
Bi .
i

i

Our intuitive understanding of length, area, and 3-dimensional volume is given by theLebesgue measure, in particular, L1 , L2 , and L3 , respectively. Note, however, that L3
cannot distinguish between a line and a plane: both have a 3-dimensional Lebesgue measureof 0. In general, Lebesgue measure in Rn provides no way to distinguish between subsets
of Rn with dimension less than n. Indeed, we do not even have a rigorous definition of
the dimension of a set (we have been relying on and will continue to rely on an intuitive
understanding of dimension until we can construct a more precise one). A generalization ofLebesgue measure, known as Hausdorff measure, is needed to avoid both these limitations.
Definition 1.2. For any subset U of Rn , the diameter of U isdiam U = sup {|x − y| : x, y ∈ U } .

FRACTALS AS FIXED POINTS OF ITERATED FUNCTION SYSTEMS

3

Definition 1.3. Let E be a subset of Rn and let {Ui } be a countable collection of setsthat cover E such that diam Ui ≤ δ for some δ > 0. For s > 0, the s-dimensional Hausdorff
measure of E is
(∞
)
∞
X
[
Hs (E) = lim inf(diam Ui )s : E ⊂Ui and diam Ui ≤ δ .
δ→0

i=1

i=1

This is similar to the Lebesgue measure. Both make use of a countable collection of setsthat cover the set we wish to measure, and then calculate its measure from the “tightest”
covering. Indeed, in Rn , Lebesgue measure and n-dimensional Hausdorff measure agree (seeTheorem 1.9 below). The Lebesgue measure, however, can only pick up n-dimensional volume, while the s-dimensional Hausdorff measure is sensitive to the volume of s-dimensional
objects living in Rn (for s < n).
As δ decreases, potential coverings using large diameters are excluded from the set of
possible coverings. Thus the infimum of this set is nondecreasing as δ decreases. This limit
therefore exists, with 0 ≤ Hs (E) ≤ ∞.
To finish establishing the definition of Hausdorff measure, we will prove that it is anouter measure. (Note that it is a fact from measure theory that an outer measure canbecome a measure if restricted to measurable sets.)
Definition 1.4. A function µ is an outer measure if it is a nonnegative function definedon all subsets of Rn such that• µ(∅) = 0,
• monotonicity: µ(A) ≤ µ(B)Sif A ⊆ B, andP∞∞• countable subadditivity: µ( i=1 Ai ) ≤ i=1 µ(Ai ) for a countable (or finite) sequence of sets {Ai }.
Theorem 1.5. The Hausdorff measure is an outer measure.
Proof. For the first condition, since the empty set is covered by any single set, the infimumof these sets has diameter 0. Hence the Hausdorff measure of the empty set is 0. For thesecond condition, note that every cover of B also covers A. Thus, the tightest cover of B
at least covers A, i.e., Hs (B) ≥ Hs (A).
ForSthe third condition, given Ai and δ, choose a set of coverings {Ui,j } such that∞Ai ⊂ j=1 Ui,j , diam Ui,j ≤ δ, and∞X(diam Ui,j )s ≤ Hs (Ai ) +j=1

for ε > 0. Then

∞
S
i=1

S∞

S S

Ui,j

i=1 Ai ⊂S∞ S∞

i=1 j=1 Ui,j . Certainly,


∞ X
∞
∞ X
∞
∞ 
X
 X
X
ε
Hs (Ai ) + i .
(diam Ui,j )s ≤(diam Ui,j )s ≤
2

i=1 Ai is covered by all Ui,j , i.e.,

inf
∞ ∞
Ai ⊂

S∞

ε
2i

i=1 j=1i=1 j=1i=1i=1 j=1

diam Ui,j ≤δIf we take the limit as δ approaches 0, we have the Hausdorff measure on the left side:
!
∞
∞ 
∞
[
X
ε X ss
HAi ≤Hs (Ai ) + i =H (Ai ) + ε.
2
i=1
i=1
i=1


4

CHRISTOPHER NATOLIIn fact, we can say even more about countable subadditivity. Since we will be working
only with Borel sets (sets constructed by countable union, countable intersection, and complementation of open and closed sets), all our sets are measurable for Hausdorff measure.
While the details of measurability do not concern us here, weSwill note that
P∞for disjoint∞
Borel sets, we have equality in countable subadditivity, i.e., µ( i=1 Ai ) = i=1 µ(Ai ).
With the definition of Hausdorff measure sufficiently established, we will proceed to
study its properties and behavior. Indeed, it has many nice properties. For instance, Hausdorff measure scales as expected:
Theorem 1.6. Let S be a similarity, i.e., a mapping S : Rn → Rn such that |S(x) −S(y)| = λ|x − y| for all x, y in Rn , with λ > 0. For a subset E of Rn ,Hs (S(E)) = λs Hs (E).
Proof. For any cover {Ui } of E with diam Ui ≤ δ, the set S(Ui ) covers S(E), anddiam S(Ui ) ≤ λδ. Then
inf
S

(
X

S(E)⊂ i S(Ui )diam S(Ui )≤λδ)(diam S(Ui ))

s

≤

X

i

(diam S(Ui ))s = λsiX(diam Ui )siand soinf
S
S(E)⊂ i S(Ui )diam S(Ui )≤λδ

(

)

(
X
(diam S(Ui ))s
i

≤

inf
S
E⊂ i Ui
diam Ui ≤δ)Xλs(diam Ui )s.

i

Letting δ approach 0, we have Hs (S(E)) ≤ λs Hs (E). Repeating the proof after switching
S with S −1 , λ with λ1 , and E with S(E), we get Hs (E) ≤ λ1s Hs (S(E)), or Hs (S(E)) ≥λs Hs (E).
Another nice property of Hausdorff measure is that for integral dimension, it agrees
with Lebesgue measure. That is to say, for an integer n, the n-dimensional Hausdorff
measure is equal to a scaling of the n-dimensional Lebesgue measure. Specifically, Ln (E) =2−n αn Hn (E), where αn is the volume of the unit n-ball.
To prove this, we will need the following two facts:
Lemma 1.7 (Isodiametric Inequality). Given a subset E of Rn with diameter d, thenvolume of E is at most the volume of a ball with diameter d, i.e., Ln (E) ≤ αn 12 d .
Lemma 1.8 (Besicovitch Covering Lemma). Let µ be a measure on Rn and E be a subset
of Rn such that µ(E) < ∞. Also, let C be a collection of nontrivial closed balls with radiusr and center x with inf {r : ball in C centered at x} = 0 for all x ∈ E. Then there exists a
countable disjoint subcollection of C that covers µ almost all of E.
We will leave these facts unproven and proceed to prove that for integral dimensions,the Lebesgue measure is just a rescaling of the Hausdorff measure.
Theorem 1.9. For any set E in Rn , we have Ln (E) = 2−n αn Hn (E).

FRACTALS AS FIXED POINTS OF ITERATED FUNCTION SYSTEMS

5

P
Proof. Choose a covering {Ui } of E such that, for ε > 0, i (diam Ui )n ≤ Hn (E) + ε. By
Lemma 1.7,n
1diam Ui
Ln (Ui ) ≤ αn
2
X
X
n
n
−n
L (E) ≤L (Ui ) ≤2 αn (diam Ui )n ≤ 2−n αn (Hn (E) + ε)ii

Ln (E) ≤ 2−n αn Hn (E).
P
We will split the converse into two cases. If Hn (E) = ∞, then i (diam Ui )n = ∞ forall
P coverings n{Ui }. In particular, for any covering by boxes Ui with diam Ui n≤ δ, we havei (diam Ui ) = ∞. Note that vol(Ui ) is just a nonzero scaling of (diam Ui ) . Therefore,
(
)
(
)
X
X
n
n
L (E) = infvol(Ui ) = inf
ki (diam Ui )
= ∞,
S
S
E⊂

i Ui

E⊂

i

i Ui

i

where ki 6= 0 are constants.
In the final case, we have Hn (E) < ∞. Given ε > 0, choose δ > 0 such that
(
)
X
[
2n
n
n
ε.
(1.10)
H (E) ≤ inf(diam Ui ) : E ⊂Ui and diam Ui ≤ δ +αnii
Let C be a covering of E by closed balls contained in E with diameter at most δ. Apply
Lemma 1.8, yielding a countable disjoint subcollection D of C, which covers Hn almost allof E. Let F be the subet of E that is covered by D, such that Hn (E \ F ) = 0. Also, let
D0 be a covering of E \ F by balls with diameter at most δ, such thatnX
1diam U
≤ ε.
αn
2
0
U ∈D

Then D ∪ D0 covers E, with diam U ≤ δ for all U ∈ D ∪ D0 . From equation (1.10),
X2n
Hn (E) ≤(diam U )n +εαnU ∈D∪D 0
n

X
1
−n
n
2 αn H (E) ≤αndiam U+ε2
U ∈D∪D 0

n
X
X
1
n
diam U+ε=
L (U ) +
αn
2
0
U ∈D

U ∈D

≤ Ln (E) + ε + ε.
(Note that thenequality above follows from that fact that each U is a ball, and consequently
αn 12 diam U = Ln (U ).)This theorem gives us some sense of what the Hausdorff measure may evaluate to, atleast for integral dimension. Like the Lebesgue measure, it may evaluate to 0 for sets
whose dimension is too low (e.g., the 2-dimensional measure of a line is 0) or infinity forsets whose dimension is too high (e.g., the 2-dimensional measure of a cube is infinity).
For sets of just the right dimension, the measure becomes meaningful.

6

CHRISTOPHER NATOLIWe can demonstrate this more rigorously. Let {Ui } be a covering of a subset E of Rn
with diam Ui ≤ δ, and let t > s. Then
X
X
X
(diam Ui )t =(diam Ui )t−s (diam Ui )s ≤
δ t−s (diam Ui )s .
i

i

i
t

Taking infima and letting δ approach 0, we find that H (E) = 0 if Hs (E) < ∞. Thus there
is a critical value s such that Ht (E) = 0 if t > s and Ht (E) = ∞ if t < s. We call thisvalue the dimension of E:
Definition 1.11. The Hausdorff dimension of a subset E of Rn isdimH E = inf {s : Hs (E) = 0} = sup {s : Hs (E) = ∞} .
Note that if s = dimH E, then Hs (E) may be zero, infinite, or some positive real number
in-between.
As an example, we will calculate the Hausdorff dimension of the Cantor set C. Its
self-similarity gives us a quick way to find its dimension, although rigor will have to besuspended until we find this value. Let CL be the left part of C, where CL = C ∩ [0, 31 ],and let CR = C ∩ [ 23 , 1] be the right part. Note that CL and CR are just scalings of C by
the ratio 13 , and that C is a disjoint union of CL and CR . Therefore,
 s
 s
1
1
s
s
s
s
H (C) = H (CL ) + H (CR ) =H (C) +
Hs (C),
3
3
by Theorem
1.6. Assuming 0 < Hs (C) < ∞ (which will be proven shortly), we have

log 2
1 s
1 = 2 3 and so s = log
3.
log 2
We must now show that Hs (C) is indeed a positive real number for s = log
3 . Define
Ek as the kth iteration toward the Cantor set. Note that it contains 2k closed intervals oflength 3−k . Then Ek covers C andlog 2

Hs (C) ≤ 2k 3−ks = 2k 3−k log 3 = 1.
To get a lower bound, let {Ui } be any covering by intervals. Expand each Ui slightly sothat it makes an open cover of C; by the compactness of C, there exists a finite subcoverof C. Thus we can assume that {Ui } is a finite collection of intervals. Define an integer kfor each Ui such that 3−(k+1) ≤ diam Ui < 3−k Since each interval of Ek is separated byat least 3−k , Ui can intersect only one interval of Ek . For j ≥ k, Ui can intersect at most2j−k = 2j 3−ks = 2j 3s 3−s(k+1) ≤ 2j 3s (diam Ui )−sintervals of Ej . Choose j large enough so that 3−(j+1) ≤ diam Ui for all Ui . Since {Ui }intersects all 2j intervals, and since each Ui intersects at most 2j 3s (diam Ui )−s intervals,
we haveX
2j 3s (diam Ui )−s ≥ 2jiX
(diam Ui )−s ≥ 3−si1.
2Hence, our assumption earlier that 0 < Hs (C) < ∞ was safe, and the dimension of thelog 2
Cantor set is indeed dimH C = s = log
3 . Note that we have also given some rough bounds
Hs (C) ≥FRACTALS AS FIXED POINTS OF ITERATED FUNCTION SYSTEMS

7

for the s-dimensional Hausdorff measure of C, namely, 12 ≤ Hs (C) ≤ 1. It can be shownthat Hs (C) = 1 (a proof of a generalization of this fact can be found in [6]).
2. Metric spaces
We must make another detour before analyzing fractals. To guarantee the existence
and uniqueness of fractals as produced by contracting similarities, we will need some tools
from the theory of metric spaces. This will allow us to more rigorously define contractions,and it will give us the necessary fixed point theorem.
Definition 2.1. A pair (X, d), where d : X × X → R, is a metric space if d satisfies• d(x, y) ≥ 0, with equality only when x = y,• d(x, y) = d(y, x), and• d(x, y) ≤ d(x, z) + d(z, y) for all z in X.
Then d is called a metric. If every Cauchy sequence in X converges, X is a complete metricspace.
Let D be a closed subset of Rn . For a subset E of D, write Nδ (E) for the δ-neighborhoodof E, i.e.,Nδ (E) = {x ∈ D : |x − a| < δ for some a ∈ E} .
Then let Ω be the set of all nonempty compact subsets of D. We associate the following
metric to Ω:
Definition 2.2. The Hausdorff metric on Ω for any A, B ∈ Ω isdH (A, B) = inf {δ : A ⊂ Nδ (B) and B ⊂ Nδ (A)} .
Theorem 2.3. The set Ω associated with the Hausdorff metric dH is a complete metricspace.
Proof. The nonnegativity of the Hausdorff metric follows from its definition. Also, let` be the least distance between any point in A and any point in B, and note thatdiam A, diam B < ∞ since A and B are bounded. Then certainly A ⊂ Ndiam A+`+diam B (B)and B ⊂ Ndiam A+`+diam B (A), so dH (A, B) ≤ diam A + ` + diam B < ∞.
For A, B elements of Ω, suppose dH (A, B) = 0 but A 6= B, i.e., there exists an x in Rnsuch that x is in A but not B, or x is in B but not A. Without loss of generality, choose
the former. If x is a distance ε > 0 away from B, then an 2ε -neighborhood of B does notcontain x and therefore does not contain A. So dH (A, B) > 2ε . Contradiction. If, on theother hand, x is not a positive distance away from B, then there exists bn in B such that|x − bn | < n1 . As n tends to infinity, bn approaches x, and thus x is in the closure of B.
Since B is closed, x is in B. Contradiction.
The symmetry of dH follows immediately from the symmetry in its definition.
Given A, B, C elements of Ω, let a be an element of A. Then there exists some b in B
such that |a − b| < dH (A, B). Similarly, there exists some c in C such that, for the b given
above, |b − c| < dH (B, C). Adding the two and applying the triangle equality for Euclidean
distance, we find that for all a, there exists some c such that|a − c| < dH (A, B) + dH (B, C).
Thus, A ⊂ NdH (A,B)+dH (B,C) (C) by definition. Following the same argument but reversing
the order, we have C ⊂ NdH (A,B)+dH (B,C) (A). Therefore, dH (A, C) ≤ dH (A, B)+dH (B, C),
and so Ω is a metric space.

8

CHRISTOPHER NATOLITo prove that it is complete, let a sequence {An } in Ω be a Cauchy sequence with respect
to the Hausdorff metric. Select a subsequence {Ak } of {An } such that dH (Ak , Ak+1 ) ≤ 2−k .
Then there exists a sequence {xk } in D, where xk is in Ak , such that|xk − xk+1 | < 2−k .
Note that {xk } is a Cauchy sequence, and since every Cauchy sequence in Rn converges,{xk } converges to some point x in D (since D is closed). By the triangle inequality, we
have
(2.4)

|xk − x| ≤ |xk − xk+1 | + |xk+1 − xk+2 | + · · · < 2−k + 2−k−1 + · · · = 2−k+1

Let A be the set of all x as defined above, i.e., all limits of sequences {xk } such thatxk is in Ak and |xk − xk+1 | < 2−k . Note that A is nonempty. Also, for any x in A, it
follows from equation (2.4) that there is some xk in Ak such that |xk − x| < 2−k+1 . Thus,
A ⊂ N2−k+1 (Ak ), and so A is bounded. If we let A be the closure of A, then A is nonempty
and compact, and so A is an element of Ω. Certainly, we also have that A ⊂ N2−k+1 (Ak ).
To achieve the converse, note that it also follows from equation (2.4) that for any xk in
Ak , there exists an x in A (and thus in A, too) such that |xk − x| < 2−k+1 . Then we have
Ak ⊂ N2−k+1 (A), and so dH (Ak , A) < 2−k+1 . Therefore {Ak } converges to A.
Since the subsequence {Ak } of the Cauchy sequence {An } converges to a point, it
follows that the whole sequence {An } also converges to the same point (proving this factin general is a standard exercise in the theory of metric spaces, so we will leave it unprovenhere).
We have now established the metric space Ω that we intend to work with. To better
study and make use of Ω, we need one more tool in the theory of metric spaces, namely atheorem guaranteeing us fixed points under a contraction.
Definition 2.5. Given a metric space X with metric d, a mapping S : X → X is acontraction ifd(S(x), S(y)) ≤ c d(x, y)
for some c < 1 and for all x, y ∈ X. If equality holds everywhere, we call S a contracting
similarity.
Theorem 2.6 (Banach’s Contraction Mapping Theorem). If X is a complete metricspace, and if S is a contraction of X into X, then there exists one and only one x in X
such that S(x) = (x).
Proof. Let x0 be an arbitrary point in X. Recursively define the sequence {xn } such thatxn+1 = S(xn ). Thend(xn+1 , xn ) = d(S(xn ), S(xn−1 )) ≤ c d(xn , xn−1 ) ≤ cn d(x1 , x0 ).
For n < m, it follows from the triangle inequality thatmXd(xn , xm ) ≤d(xi , xi−1 )
≤

i=n+1
m
X
i=n+1
n

≤

ci−1 d(x1 , x0 )cd(x1 , x0 ).
1−cFRACTALS AS FIXED POINTS OF ITERATED FUNCTION SYSTEMS

9Since c < 1, d(xn , xm ) approaches 0 for large n, and so {xn } is a Cauchy sequence. Since
X is complete, {xn } converges to some x = lim xn in X.
n→∞Note that S is continuous since it is a contraction. Therefore,S(x) = S lim xn = lim S(xn ) = lim xn+1 = x,
n→∞

n→∞

n→∞

and so x is indeed a fixed point.
To prove the uniqueness of x, suppose that there exists a second fixed point y. Notethat d(S(x), S(y)) ≤ c d(x, y). Since S(x) = x and S(y) = y, we have d(x, y) ≤ c d(x, y).
This implies that d(x, y) = 0, or x = y.

3. Iterated function systems
The fractals we are interested in studying are all self-similar, i.e., they are made up
of several contracted copies of themselves. Clearly, fractals are fixed points under thesecontractions. We will use the concept of iterated function systems, under which fixed points
are called attractors, to formalize this method of constructing fractals.
Definition 3.1. An iterated function system (abbreviated “IFS”) is a collection of contractions {S1 , S2 , . . . , Sm }, with m ≥ 2, on a closed subset D of Rn . A nonempty compact
subset F of D is an attractor of the IFS ifm[
Si (F ).
F =i=1

Let us consider the Cantor set C as an example of a fractal that can be describedthrough an IFS. Let D be the interval [0, 1] and define the IFS as the contractions
11andS2 (x) = 1 − x.
(3.2)
S1 (x) = x
33Note that S1 (C) produces the left half of the Cantor set and S2 (C) produces the righthalf. Thus their union is the Cantor set and, indeed, the Cantor set is the attractor of thisIFS.
An important property of IFSs is that each IFS hasSa unique attractor. To prove this,m
we will apply Theorem 2.6 to the contraction S(·) = i=1 Si (·) on the complete metricspace Ω.
Theorem 3.3. Given an IFS defined by contractions {S1 , . . . , Sm } on a closed subset D
of Rn , let ΩSbe the set of all nonempty compact subsets of D, and for an element E of Ω,mlet S(E) = i=1 Si (E). Then there exists a unique attractor F of the IFS, i.e., a uniqueset F such that S(F ) = F . Furthermore, for every set E in Ω such that S(E) ⊂ E, we
have
∞
\
F =
S k (E),k=0kwhere S (E) = S(S(· · · (S (E)))) is the kth iterate of S.
| {z }
k times

Proof. Let dH be the Hausdorff metric (see Definition 2.2). Note that if Si (A) ⊂ Nδ (Si (B))
for all i, then
!
m
m
m
[
[
[
Si (A) ⊂Nδ (Si (B)) = NδSi (B) .
i=1

i=1

i=1

10

CHRISTOPHER NATOLI(The same holds
Smif you swap
SmA with B.) Thus, if δ is such that dH (Si (A), Si (B)) < δ forall i, then dH ( i=1 Si (A), i=1 Si (B)) < δ. Therefore,
!
m
m
[
[
dH
Si (A),Si (B) ≤ max dH (Si (A), Si (B))
i=1

1≤i≤m

i=1


(3.4)

≤


max ci dH (A, B),1≤i≤msince Si is a contraction. Thus we have dH (S(A), S(B)) ≤ (maxi ci ) dH (A, B), and sincemaxi ci < 1, then S is also a contraction on Ω. From Theorem 2.3, we know that Ω is acomplete metric space, and so by Theorem 2.6, S has a unique fixed point F in Ω.
It follows from the proof ofTheorem 2.6 that S k (E) approaches F as k tends to infinity.
Note that if S(E) ⊂ E, then S k (E) is a decreasing sequence of nonempty compact sets
T∞
containing F . Therefore, their intersection i=1 S(E) = F .
This theorem holds for all contractions, not only contracting similarities. But if we
restrict our focus to similarities, we can say a lot more about the attractors guaranteedby this theorem. In particular, we can easily calculate its Hausdorff dimension. We haveseen an example of calculating the dimension of self-similar fractals at the end of Section
1, for the Cantor set. It was key to this calculation that the Cantor set is made up of
two disjoint scaled copies of itself. However, we can slightly relax this condition and only
require the following.
Definition 3.5. An IFS of similarity contractions {S1 , . . . , Sm } satisfies the open set
condition if there exists a nonempty bounded open set V such thatm[
Si (V ),
V ⊃i=1

with this union disjoint.
Note that the IFS that produces the Cantor set (see equations (3.2)) satisfies the open set
condition, with V = (0, 1).
Before we can prove a formula to calculate the dimension of self-similar sets, we willneed the following lemma.
Lemma 3.6. Let {Vi } be a collection of disjoint open subsets of Rn such that each Vi
contains a ball of radius a1 r and is contained in a ball of radius a2 r. Then any ball B ofradius r intersects at most (1 + 2a2 )n a−nof the closures Vi .
1
Proof. If Vi intersects B, then Vi is certainly contained in a ball of radiusr + diam Vi ≤ (1 + 2a2 )rcentered at the center of B. Suppose that q of the sets Vi intersect B. Then a single ballof radius (1 + 2a2 )r contains all q sets Vi and thus contains q balls of radius a1 r. Adding
up the volumes of these q interior balls, we haveq(a1 r)n ≤ (1 + 2a2 )n rn
q ≤ (1 + 2a2 )n a−n
1 .

We will also need the following lemma about mass distributions.

FRACTALS AS FIXED POINTS OF ITERATED FUNCTION SYSTEMS

11

Definition 3.7. A measure µ on a set X is a mass distribution if 0 < µ(X) < ∞. For
any subset A of X, we call µ(A) the mass of A.
Lemma 3.8 (Mass distribution principle). Let µ be a mass distribution on F such thatfor some s, there exists c, δ > 0 such thatµ(U ) ≤ c(diam U )s

(3.9)

for all sets U with diam U ≤ δ. Then Hs (F ) ≥ µ(F )/c and s ≤ dimH F .
Proof. Let {Ui } be a cover of F with diam Ui ≤ δ. Then, by the properties of measuresand equation (3.9),!
[
XXµ(F ) ≤ µ
Ui ≤µ(Ui ) ≤ c(diam Ui )s .
iii

Taking the infimum and letting δ tend to 0, we have Hs (F ) ≥ µ(F )/c. Since µ(F ) > 0, we
have dimH F ≥ s.

We can now prove a formula to calculate the dimension of self-similar sets defined by
IFSs. This will be similar to our calculation of the dimension of the Cantor set, in that wemust determine lower and upper bounds for the Hausdorff measure of such a set.
Theorem 3.10. Suppose an IFS of contracting similarities {S1 , . . . , Sm } satisfies the open
set condition, and let ci be the ratio of each similarity Si . Let F be the attractor of thisIFS. Then dimH F = s, wheremX(3.11)
csi = 1.
i=1sAlso, we have 0 < H (F ) < ∞.
Proof. Define s according to equation (3.11). Let Ik be the set of all sequences (i1 , . . . , ik )where ij ∈ {1, . . . , m}. Also, for any set A and a given sequence (i1 , . . . , ik ) in Ik , define
Ai1 ,...,ik = Si1 ◦ · · · ◦ Sik (A). Then since F is a fixed point under the IFS, we have[F =Fi1 ,...,ik .
Ik

Thus the sets {Fi1 ,...,ik } cover F . Note that the mapping Si ◦ · · · ◦ Sk is a contracting
similarity with ratio ci1 · · · cik . Therefore,
X
X(diam Fi1 ,...,ik )s =(ci1 · · · cik )s (diam F )s
Ik

Ik

=
(3.12)

X
X 
csi1 · · ·csik (diam F )s= (diam F )sby equation (3.11). For all δ > 0, we can choose k large enough that (maxi ci )k diam F ≤ δ.
Since diam Fi1 ,...,ik ≤ (maxi ci )k diam F , the sets {Fi1 ,...,iP} cover F with diam Fi1 ,...,ik ≤ δ
kfor all sequences (ii , . . . , ik ) in Ik . Therefore, Hs (F ) ≤ Ik (diam Fi1 ,...,ik )s = (diam F )sby equation (3.12).
We will now try to determine a lower bound for Hs (F ). Let I be the set of all infinite
sequences (i1 , i2 . . .) with ij ∈ {1, . . . , m}, and let Ii1 ,...,ik be the subset of I consisting
only of sequences starting with i1 , . . . , ik . Then define a mass distribution µ on I letting

12

CHRISTOPHER NATOLIsµ(IPmii ,...,ik ) = (ci1 · · · cik ) . Proving that µ is indeed a measure follows immediately from
i=1 µ(Iii ,...,ik ,i ) = µ(Iii ,...,ik ). It also follows from equation (3.11) that µ(I) = 1, and soµ is a mass distribution.
T∞
Define a point xi1 ,i2 ,... in F as xi1 ,i2 ,... = k=1 Fi1 ,...,ik . Then for a subset A in F , define
a new mass distribution µ̃ based on µ by letting µ̃(A) = µ({Ii1 ,...,ik : xi1 ,...,ik ,... ∈ A}).
Intuitively, the µ̃-mass of a set is the µ-mass of the sequences that define the points
in that set. Note that µ̃(F ) = µ(I) = 1 since F contains every point xi1 ,i2 ,... for each
(i1 , i2 , . . .) in I.
We now want to show that µ̃ satisfies the conditions of Lemma 3.8, which will provide us with the desired lower bound. Let S
V be the open set guaranteed by the openm
set condition (see Definition 3.5), i.e., V ⊃ i=1 Si (V) with this union disjoint. Letting
Sm
S(V ) = i=1 Si (V ), it follows from Theorem 3.3 that S k (V ) converges to F . Therefore,
V i1 ,...,ik ⊃ Fi1 ,...,ik for any sequence (i1 , . . . , ik ).
Let B be a ball of radius r < 1 that intersects F . Also, truncate each sequence (i1 , i2 , . . .)in I after the first ik at which point(3.13)
min ci r ≤ ci1 ci2 · · · cik ≤ r,1≤i≤mwhere c1 , . . . , cm are the ratios of the m contracting similarities. Let Q be the finite setof all such truncated sequences. Since V1 , . . . , Vm are disjoint, Vi1 ,...,ik ,1 , . . . , Vi1 ,...,ik ,m aredisjoint too, and thus all sets Vii ,...,ik where (i1 , . . . , ik ) is a sequence in Q are also disjoint.
Furthermore,[[[
V i1 ,...,ik .
(3.14)F =Fi1 ,i2 ,... ⊂Fi1 ,...,ik ⊂I

Q

Q

Choose a1 and a2 such that V contains a ball of radius a1 and is contained in a ball ofradius a2 . Then for all (i1 , . . . , ik ) in Q, the set Vi1 ,...,ik contains a ball of radius ci · · · ck a1
and is contained in a ball of radius ci · · · ck a2 . By equation (3.13), every Vi1 ,...,ik contains
a ball of radius (mini ci r)a1 and is contained in a ball of radius ra2 . Let Q0 be the subset
of Q consisting only of sequences (i1 , . . . , ik ) such that V i1 ,...,ik intersects B. By Lemma
3.6, there are at most q = (1 + 2a2 )n (mini ci a1 )−n elements in Q0 .
Taking the µ̃-mass of B,µ̃(B) = µ̃(F ∩ B)
= µ({Ii1 ,...,ik : xi1 ,...,ik ,... ∈ F ∩ B})(!
)!
[
V i1 ,...,ik ∩ B≤µ
Ii1 ,...,ik : xi1 ,...,ik ,... ∈Q

since F ⊂S

0
Q V i1 ,...,ik by equation (3.14). From the definition of Q , we have(µ̃(B) ≤ µ)!

Ii1 ,...,ik : xi1 ,...,ik ,... ∈[V i1 ,...,ik

!
=µ

Q0

[

Ii1 ,...,ik.

Q0

Finally, it follows from the properties of the mass distribution µ and equation (3.13) that
X
X
X
µ̃(B) ≤µ(Ii1 ,...,ik ) =(ci1 · · · cik )s ≤rs = qrs .
Q0

Q0

Q0

FRACTALS AS FIXED POINTS OF ITERATED FUNCTION SYSTEMS

13

It follows that, for any set U contained in a ball BU of radius diam U , we have µ̃(U ) ≤µ̃(BU ) ≤ q(diam U )s . Then by Lemma 3.8, Hs (F ) ≥ µ(F )/q = 1/q > 0. Thus Hs (F ) is apositive real number and so dimH F = s.
This theorem provides quick ways to calculate dimension of self-similar fractals. Take theCantor set for example. The IFS for which the Cantor set is an attractor is S1 (x) = 31 x
and S2 (x) = 1 − 13 x; as demonstrated above, this satisfies the open set condition with
V = (0, 1).
3.10, the Hausdorff dimension of the Cantor set is s such
s Thus by Theorem
log 2
.
Note
that this is similar to our previous calculation of thethat 2 13 = 1, or s = log
3dimension of the Cantor set in Section 1.
We can use this theorem to calculate the dimension ofmany other self-similar fractals. For example, to construct
the von Koch curve, replace the middle third of a straightline segment with the other two sides of an equilateral triangle erected on this middle third (see Figure 2). For each iteration, repeat this procedure for every segment in the curve. Figure 2. The first itera(For the resulting fractal, see Figure 3.) Clearly, the contract- tion of the von Koch curve.
ing similarities are of ratio 13 . The open set condition holdswith V as the interior of the tightest isosceles triangle that√
contains the von Koch curve, i.e., with the initial segment as the base and a height of 63s
4times the length of the base. Then the dimension s satisfies 4 13 = 1, and so s = log
log 3 .

Figure 3. The von Koch curve.
We can also use this theorem in reverse. Given a number to be the dimension of a fractal, we can construct an
IFS that has as its attractor a fractal with this dimen16
1 ssion. We will choose s = 43 = log= 1. Forlog 8 , or 16 8
aesthetics, we will choose the initial iteration displayedin Figure 4, which contains sixteen segments of length 18
the total width, thus satisfying the requirements of ourchosen dimension. As with the von Koch curve, replace
Figure 4. The first iterationeach segment with a copy of the curve scaled by the choof a fractal with dimension 43 .
sen similarity ratio 18 , yielding the fractal in Figure 5.
(The images in Figures 2 through 5 were produced with the program included in the
Appendix.)

14

CHRISTOPHER NATOLI

Figure 5. A fractal with dimension 34 .
4. Fractals in dynamical systems
Given the iterative nature of fractals, it is not surprising that they show up in dynamicalsystems, in which a function is iterated repeatedly on a set, with each iteration representing
another step in time. To better explore the use of fractals in dynamical systems theory,
we must set up the following definitions.
Definition 4.1. Given a continuous mapping f : D → D on a subset D of Rn , let f kdenote the kth iterate of f . Then the system described by the iterations of f on D is akdiscrete dynamical system. For a given initial point x in D, the infinite
 sequence fp−1(x) iskan orbit. If f (x) settles into an orbit that is a finite set of points w, f (w), . . . , f(w) ,where p is the least positive number such that f p (w) = w, then this set of points is anorbit of period-p points.
It may be the case that f k (x) settles into an orbit of period-1 points, i.e., settles upona fixed point f (w) = w. The iterates f k (x) might also seem to jump about randomly, all
the while approaching a certain set (indeed, often a fractal). To further discuss the sets towhich iterates converge, we will need more terminology.
Definition 4.2. A subset F of D is an attractor for f if F is a closed set such that• f (F ) = F ;• for all x in an open set V containing F , the distance between f k (x) and F converges
to zero as k tends to infinity; and• for any other set G satisfying the above two conditions, F ⊂ G.
Likewise, F is a repeller if F satisfies the above conditions with the second condition
modified so that the distance between f k (x) and F diverges as k tends to infinity.
Intuitively, an attractor is a sink. To use a power grid as an example, a house is an
attractor, taking energy from a region of the grid surrounding it. This region may besmall, depending on how close other houses are. Extending the analogy, the power station
is a repeller.
A key concern of dynamical systems theory is the behavior of the function f , and inparticular, whether it is chaotic. We will use the following definition.
Definition 4.3. Given a continuous mapping f : D → D on a subset D of Rn , withattractor or repeller F , we say that f exhibits chaotic behavior on F if

FRACTALS AS FIXED POINTS OF ITERATED FUNCTION SYSTEMS

15

• for some x in F , the orbit f k (x) is dense in F ;• the periodic points of f in F are dense in F ; and• f has a sensitive dependence on inital conditions, i.e., there exists δ > 0 such thatfor all x in F , there exists y in F arbitrarily close to x such that |f k (x)−f k (y)| ≥ δfor some k.
The choice of the word chaotic follows from the fact that f thoroughly “mixes up”
points in F , and that a small change in the initial value of x can result in a large change
in f k (x). The “butterfly effect”—that a butterfly flapping its wings in Brazil can produce
a tornado in Texas—follows from this.
With our terminology now established, we will study the Cantor set as an example offractals arising in dynamical systems. In this particular case, the Cantor set is both theattractor of an IFS and the repeller of a dynamical system. Furthermore, the function
describing the dynamical system exhibits chaotic behavior in the Cantor set.
The function of interest is3
f (x) = (1 − |2x − 1|).
2
If we describe the IFS by the contractions S1 , S2 : [0, 1] → [0, 1], given by S1 (x) = 31 x andS2 (x) = 1 − 13 x, we find that f inverts both S1 and S2 on [0, 1], i.e.,f (S1 (x)) = f (S2 (x)) = x.
Theorem
3.3 guarantees that there exists a unique attractor C for this IFS, and C =T∞k
k=0 S ([0, 1]), where S = S1 ∪ S2 . Indeed, C is the Cantor set.
We will first establish that C is a repeller for f . Since C is an attractor of the IFS, wehave
C = S(C) = S1 (C) ∪ S2 (C)f (C) = f (S1 (C)) ∪ f (S2 (C))= C ∪ C = C,
and so C satisfies the first condition of being a repeller (see Definition 4.2). Furthermore,note that for x < 0, we have3f (x) = (1 + (2x − 1)) = 3x,2
and so f k (x) = 3k x. Therefore, f k (x) → −∞ as k → ∞. For x > 1, we have3
(1 − (2x − 1)) = 3(1 − x).
2
Clearly, f (x) < 0 for all x > 1, and so just one iteration of f brings us to the previous
case, in which x < 0. Thus, again, f k (x) → −∞ as k → ∞. For the final case, namelyx ∈ [0, 1] \ C, there exists some k such that x ∈/ S k ([0, 1]), i.e.,[x∈/{Si1 ◦ Si2 ◦ · · · ◦ Sik ([0, 1]) : ij = 1, 2}[
f (x) ∈/
{Si2 ◦ Si3 ◦ · · · ◦ Sik ([0, 1]) : ij = 1, 2}
f (x) =..
.
f k (x) ∈/ [0, 1].

16

CHRISTOPHER NATOLIWe therefore return to one of the two previous cases, and so f k (x) → −∞. In sum, frepels all x ∈/ C to −∞, and the second condition is satisfied.
To prove the final condition, that C is minimal, suppose that C = G1 ∪ G2 with thisunion disjoint and with G1 a repeller under f . Note that for all i, we have Si (G2 )∩G1 = ∅,since if Si (G2 ) and G1 did share some point x, then both f (x) ∈ f (Si (G2 )) = G2 andf (x) ∈ f (G1 ) = G1 , which is impossible since G1 and G2 are disjoint.
S∞ Since S(G2 ) ⊂ C
but S(G2 ) ∩ G1 = ∅, it must be that S(G2 ) ⊂ G2 . But G2 ⊃ k=1 S k ( G2 ) = C by
Theorem 3.3. Contradiction.
We also wish to prove that f is chaotic in C. Let E in Ω be such that Si (E) ⊂ E fori = 1, 2. Recall that from Theorem 3.3,
C=∞\

S k (E)k=0

for all such E. Thus, for any x ∈ C, we have x ∈ Si1 ◦ · · · ◦ Sik (E) for some sequence(i1 , . . . , ik ) with ij = 1, 2. Extending this sequence gives us a way to express x, namely,x=∞\

Si1 ◦ · · · ◦ Sik (E).

k=1

We will denote this by x = xi1 ,i2 ,... . Observe, first, that this notation is independent of E,
and, second, that for any two points xi1 ,i2 ,... and xi01 ,i02 ,... in C such that i1 = i01 , . . . , ik =
i0k , we have|xi1 ,i2 ,... − xi01 ,i02 ,... | ≤ 3−k .
The latter follows from the fact that Si1 is applied last, Si2 is applied second-to-last, andso forth. Also note that xi1 ,i2 ,... = S1 (xi2 ,i3 ,... ), and so f (xi1 ,i2 ,... ) = xi2 ,i3 ,... ,For `j = 1, 2, let (`1 , `2 , . . .) be a sequence containing every n-term sequence of 1sand 2s for all n, e.g., (1, 2, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1, 1, 1, 1, 2, . . .). Thenfor any point xi1 ,i2 ,... in C and for all positive integers q, there exists a k such thati1 = `k+1 , . . . , iq = `k+q . Therefore,|xi1 ,i2 ,... − x`k+1 ,`k+2 ,... | ≤ 3−q|xi1 ,i2 ,... − f k (x`1 ,`2 ,... )| ≤ 3−q .
That is to say, for any point xi1 ,i2 ,... in C, the iterates f k (x`1 ,`2 ,... ) are arbitrarily close toxi1 ,i2 ,... if q and k are sufficiently large. Therefore, f k (x`1 ,`2 ,... ) make up dense orbits in C,
satisfying the first condition of chaotic behavior.
In addition, the periodic points x`1 ,...,`p ,`1 ,...,`p ,`1 ,... are dense in C, since for any xi1 ,i2 ,...
in C, one can construct a periodic point x`1 ,`2 ,...,`k ,...,`p ,`1 ,... such that i1 = `1 , . . . , ik = `k ,and therefore|xi1 ,i2 ,... − x`1 ,`2 ,... | ≤ 3−k .
Periodic points can thus be made arbitrarily close to any other point in C, and thus theperiodic points are, too, dense in C.
The final condition, that f has a sensitive dependence on initial conditions, is easy toshow. Consider two points xi1 ,i2 ,... and xi01 ,i02 ,... arbitrarily close to each other, as provided
by i1 = i01 , . . . , ik = i0k . Let ik+1 = 1 and i0k+1 = 2. Then
and f k (xi01 ,i02 ,... ) = x2,i0k+2 ,... ∈ 23 , 1 .
f k (xi1 ,i2 ,... ) = x1,ik+2 ,... ∈ 0, 31

FRACTALS AS FIXED POINTS OF ITERATED FUNCTION SYSTEMS

17

That is to say, there exists a δ = 13 > 0 such that, given a point xi1 ,i2 ,... , there exists anarbitrarily close point xi01 ,i02 ,... in C such that|f k (xi1 ,i2 ,... ) − f k (xi01 ,i02 ,... )| = |x1,ik+2 ,... − x2,i0k+2 ,... | ≥ δ.
This satisfies the third condition of chaotic behavior.
Acknowledgments. It is a pleasure to thank my mentor, Max Engelstein, for his guidance and feedback during the research and writing that led to this paper. His enthusiasm
for the material, challenging expectations, and constant patience and support were instrumental to writing this paper and making it an instructive and enjoyable experience. I
would also like to thank Professor Peter May for his generous support in organizing the
University of Chicago REU, which has made this all possible.
References[1] Kenneth Falconer. Fractal Geometry: Mathematical Foundations and Applications. John Wiley & Sons,
2003.
[2] Frank Morgan. Geometry Measure Theory. Academic Press, 2009.
[3] Walter Rudin. Principles of Mathematical Analysis. McGraw-Hill, 1964.
[4] William P. Ziemer. Modern Real Analysis. http://www.scribd.com/doc/16597427/24/Hausdor%EF%AC%80-Measure[5] Kenneth Falconer. The Geometry of Fractal Sets. Cambridge University Press, 1985.
[6] Shipan Lu. The Hausdorff Dimension and Measure of Some Cantor Sets. Real Analysis Exchange,
Volume 25, Number 2 (1999).
[7] Jeff Henrikson. Completeness and Total Boundedness of the Hausdorff Metric. MIT Undergraduate
Journal of Mathematics. www-math.mit.edu/phase2/UJM/vol1/HAUSF.PDF[8] Michael Slone, Chi Woo. Hausdorff metric inherits completeness. PlanetMath.org.
http://planetmath.org/HausdorffMetricInheritsCompleteness.html.
[9] Margherita Barile and Eric W. Weisstein. Cantor Set. MathWorld–A Wolfram Web Resource.
http://mathworld.wolfram.com/CantorSet.html

Appendix
The images in Figures 2 through 5 were produced with the following Python program.
# This program was designed and written by Christopher Natoli.
# It makes use of the Pyglet library to handle graphics and user interface.
# It can be run with Python 2.7.
import mathimport pyglet
from pyglet.gl import *################################################################################# helper functions
def tuple_scale(tup, ratio):
return tuple([elem*ratio for elem in tup])
def increment_pair(pair, val0, val1):
return (pair[0]+val0, pair[1]+val1)
def increment_list(li, val0, val1):

18

CHRISTOPHER NATOLI

return [increment_pair(pair, val0, val1) for pair in li]################################################################################# geometric functions
def find_angle(a,b):
if a[0]==b[0] and a[1]==b[1]: # same point
return -100
return math.atan2(b[1]-a[1], b[0]-a[0])def rotate_pt(pt, theta): # uses a rotation matrix
return ( pt[0]*math.cos(theta)-pt[1]*math.sin(theta),
pt[0]*math.sin(theta)+pt[1]*math.cos(theta) )################################################################################# fractal class ("Frack") and some examples
class Frack:
def __init__(self, vertices, segments):
self.vertices = vertices
self.segments = segments
def scale(self, ratio):
return Frack([tuple_scale(point, ratio) for point in self.vertices],
self.segments)
def rotate(self, theta):
return Frack([rotate_pt(point, theta) for point in self.vertices],
self.segments)
quad_koch = Frack( [ (0.0, 0.25), (0.25, 0.25), (0.25, 0.0),(0.5, 0.0), (0.5, 0.25), (0.5, 0.5),(0.75, 0.5), (0.75, 0.25), (1.0, 0.25) ],[ (0,1), (1,2), (2,3), (3,4), (4,5), (5,6), (6,7), (7,8) ])treelike = Frack( [ (0.0, 0.333), (0.333, 0.333), (0.333, 0.666),(0.666, 0.333), (0.666, 0.0), (1.0, 0.333) ],[ (0,1), (1,2), (1,3), (3,4), (3,5) ])koch = Frack( [ (0.0, 0.0),(0.333, 0.0),(0.5, 0.2887),(0.666, 0.0),(1.0,0.0) ],[ (0,1), (1,2), (2,3), (3,4) ])square_koch = Frack( [ (0.0, 0.0), (0.333, 0.0), (0.333, 0.25),(0.666, 0.25), (0.666, 0.0), (1.0, 0.0) ],[ (0,1), (1,2), (2,3), (3,4), (4,5) ])FRACTALS AS FIXED POINTS OF ITERATED FUNCTION SYSTEMS

19

seong = Frack( [ (0.0, 0.2165), (0.125, 0.2165), (0.25, 0.2165),(0.1875, 0.32476), (0.3125, 0.32476), (0.375, 0.433),(0.4375, 0.32476), (0.5625, 0.32476), (0.5, 0.2165),(0.4375, 0.10825), (0.5625, 0.10825), (0.625, 0.0),(0.6875, 0.10825), (0.8125, 0.10825), (0.75, 0.2165),(0.875, 0.2165), (1.0, 0.2165)],[ (0,1), (1,2), (2,3), (3,4), (4,5), (5,6), (6,7), (7,8),(8,9), (9,10), (10,11), (11,12), (12,13), (13,14), (14,15),(15,16) ])################################################################################# fractal functions
def center_generator(gen):#lower all points in generator by y-value of first pt
return Frack(increment_list(gen.vertices, 0, -gen.vertices[0][1]),gen.segments)
def iterate(generator, iteration):
new_vertices = []new_segments = []for seg in iteration.segments:
a = iteration.vertices[seg[0]]b = iteration.vertices[seg[1]]theta = find_angle(a,b)
if theta==-100:
print("Error in finding angle.")returnleng = math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)
copy = center_generator(generator.scale(leng)).rotate(theta)
new_segments.extend(increment_list(copy.segments,len(new_vertices),len(new_vertices)))
new_vertices.extend(increment_list(copy.vertices, a[0], a[1]))return Frack(new_vertices, new_segments)################################################################################# drawing and graphics functions
width = 900
height = 700
window = pyglet.window.Window(width,height)
glClearColor(1,1,1,1) # white background20

CHRISTOPHER NATOLI

def draw_line(a,b):
glColor4f(0,0,0,1.0)
glBegin(GL_LINES)
glVertex2f(a[0],a[1])glVertex2f(b[0],b[1])glEnd()
def max_height(frack):
max_so_far = 0
for point in frack.vertices:
if point[1] > max_so_far:
max_so_far = point[1]return max_so_far
def center_frack(frack):
y_offset = (height/2) - (max_height(frack)/2)
return Frack(increment_list(frack.vertices,0,y_offset),frack.segments)
def draw_frack(frack): # draws single iteration only
for seg in frack.segments:
draw_line(frack.vertices[seg[0]],frack.vertices[seg[1]])def draw_fractal(gen):current_iter = center_frack(gen.scale(width))for i in range(4): # user can choose number of iterations here
glClear(GL_COLOR_BUFFER_BIT)
current_iter = iterate(gen, current_iter)
draw_frack(current_iter)@window.event
def on_draw():
glClear(GL_COLOR_BUFFER_BIT)############################# user can choose which fractal to draw by uncommenting only
# the desired fractal#draw_fractal(quad_koch)#draw_fractal(treelike)#draw_fractal(koch)#draw_fractal(square_koch)
draw_fractal(seong)############################
pyglet.image.get_buffer_manager().get_color_buffer().save(’screenshot.png’)# the image will be saved as a file called ’screenshot.png’

FRACTALS AS FIXED POINTS OF ITERATED FUNCTION SYSTEMS

21

pyglet.app.run()This program produces fractals from user-specified generators (i.e., the first iterationsof fractals). To produce the next iteration, it scales and then copies the generator onto
each segment of the previous iteration. The contractions of the IFS are determined by thelengths of the segments of the generator.
This program is designed to be flexible so that users may create their own fractals. To
do so, users must specify the details of the generator, namely, the locations of the vertices
and which vertices are connected by segments. This is done by writing an instance of the
Frack class. The variables quad_koch, treelike, koch, square_koch, and seong are all
examples of generators (koch produced the fractal in Figure 3 and seong produced thefractal in Figure 5). The total width of the generator must be 1. There are no restrictions
on the height, although it is expected that the fractal will be wider than it is high (this canbe changed, however, by changing the dimensions of the image as defined by the widthand height variables). The lowest point on the generator must have a y-coordinate of 0.0.
The segments list in the Frack class determines which points of the vertices list areconnected. Note that this program was written with fractals only produced from segments
in mind. Also note that the program may take some time to draw the iterations. One canreduce this time by reducing the number of iterations drawn (it is currently set at 4).