Graphics Reference
In-Depth Information
We can now describe a way to generalize Algorithms 22.4.1 and 22.4.2 (and also
the chaos game construction in Programming Project 1.5.5). The key elements are
captured by the following definition:
Definition.
An
iterated function system
, or
IFS
for short, is a pair ((
X
,d),W), where
(
X
,d) is a complete metric and W = {w
1
,w
2
,...,w
k
} is a finite set of contraction maps
w
i
:
X
Æ
X
. The
contractivity factor
c of this system is defined by
{
}
c
=
max
c
,
c
,. . . ,
c
k
,
12
where c
i
is the contractivity factor of w
i
. An
iterated function system with probabilities
is a tuple ((
X
,d),W,P}, where ((
X
,d),W) is an IFS and P = {p
1
,p
2
,...,p
|W|
} is a set of
probabilities, that is,
p
>
0
and
p
+
p
+
...
+
p
=
1
.
i
1
2
w
22.4.4
Theorem.
Let ((
X
,d),W) be an IFS with contraction factor c. Define
()
Æ
()
wH
W
:
XX
H
by
U
()
=
()
w
B
w
B
.
W
wW
Œ
Then the map w
W
is a contraction map on (H(
X
),d
H
) with contractivity factor c. Fur-
thermore, the unique fixed point
A
of w
W
, called the
attractor
of the IFS ((
X
,d),W),
satisfies
U
()
(1)
A
=
w
wW
, and
Œ
n
(
B
(2)
A
=
lim
n
w
for any
B
ΠH (
X
).
W
Æ•
Proof.
See [Barn88].
It is the theory behind Theorem 22.4.4 that explains the “deterministic” Algorithm
22.4.1. We refer the reader to Barnsley's topic for the theorem that corresponds to
Theorem 22.4.4 in the case of iterated function systems with probabilities and the “non-
deterministic” Algorithm 22.4.2. It involves technicalities of measure theory that would
take us past the level of our presentation here. Nevertheless, it is the study of iterated
function systems with probabilities that really leads to an understanding of fractals.
We move on in our discussion of “deterministic” IFSs in order to state the fun-
damental theorem in this topic.
Definition.
Let (
X
,d) be a complete metric space and let
A
ΠH(
X
) . The map w:
H(
X
) Æ H(
X
) defined by w(
B
) =
A
,
B
ΠH(
X
), is called a
condensation transformation
of
X
and
A
is called its
condensation set
.
