The Chaos Game: Address Space vs IFS
The Chaos Game is a way of constructing a deterministic object, like Sierpinski's gasket, by a random process in which a pattern emerges out of an apparently chaotic distribution of points. The chaos game applies to the attractor, a fixed point, of any iterated function system. Sierpinski's gasket is an easiest example.
The simplest(*) iterated function system whose attractor is the Sierpinski gasket consists of three contractions FA, FB, FC, with fixed points at the vertices of a given triangle ABC and coefficient 1/2. (I shall use FA, FB, FC and F1, F2, F3 interchangeably, depending as to what notation is more convenient at the instance.)
Why does the chaos game work? First of all, let's observe that the three triangles obtained on the first step of the trema removal procedure are the images of the three contractions:
T1 = F1(T0), T2 = F2(T0), T3 = F3(T0),
where T0 is the triangle ABC. In a concise form we can write
|(1)||Tσ1 = Fσ1(T0),|
where s1 is one of the symbols 1, 2, 3. For a second application,
Fσ2(Fσ1(T0)) = Fσ2(Tσ1) ⊂ Fσ2(T0) = Tσ2.
In other words, the image of T0 after two steps (first applying Fσ1 and then Fσ2) is inside Tσ2 and is obviously one of the three triangles into which the latter is split on the second construction step, viz., the triangle corresponding to the index s1. In our addressing notations, this is triangle Tσ2σ1:
|(2)||Fσ2(Fσ1(T0)) = Tσ2σ1.|
Similarly, for a third application, we get
|(3)||Fσ3(Fσ2(Fσ1(T0))) = Tσ3σ2σ1.|
We see (and this can be shown rigorously by induction) that the triangle
|(n)||Ts1s2...sn = Fs1(Fs2(...(Fsn(T0)...)).|
The sequence of triangles Tsn, ..., Ts2...sn, Ts1s2...sn thus obtained differs from the nested sequence Ts1, Ts1s2, ..., Ts1s2...sn in the trema removal procedure, but, however surprisingly, the final triangle is the same.
This fact is illustrated by the applet below. By pressing buttons A, B, C you execute an application of the corresponding contractions. The applet can display the sequence of triangles obtained by successive application of these transforms, or those coming from the addressing scheme.
|What if applet does not run?|
Since, for any transformation F, x ∈ T implies
- M. Barnsley, Fractals Everywhere, Academic Press, 1988
- The Science of Fractal Images, H.-O.Peitgen and D.Daupe (eds), Springer-Verlag, 1988
- H.-O. Peitgen, H. Jürgens, D. Saupe, Chaos and Fractals: New Frontiers of Science, Springer-Verlag, 1992
(*) As an example, the iterated system FAFA, FAFB, ..., FCFC that consists of 9 contractions each with coefficient 1/4, has exactly the same attractor as the system of three functions FA, FB, FC. For a demonstration, see the applet at the Collage Theorem and IFS page and play with the Iterate button.