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 F_{A}, F_{B}, F_{C}, with fixed points at the vertices of a given triangle ABC and coefficient 1/2. (I shall use F_{A}, F_{B}, F_{C} and F_{1}, F_{2}, F_{3} 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:
T_{1} = F_{1}(T_{0}), T_{2} = F_{2}(T_{0}), T_{3} = F_{3}(T_{0}),
where T_{0} is the triangle ABC. In a concise form we can write
(1) | T_{σ1} = F_{σ1}(T_{0}), |
where s_{1} is one of the symbols 1, 2, 3. For a second application,
F_{σ2}(F_{σ1}(T_{0})) = F_{σ2}(T_{σ1}) ⊂ F_{σ2}(T_{0}) = T_{σ2}.
In other words, the image of T_{0} 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 s_{1}. In our addressing notations, this is triangle T_{σ2σ1}:
(2) | F_{σ2}(F_{σ1}(T_{0})) = T_{σ2σ1}. |
Similarly, for a third application, we get
(3) | F_{σ3}(F_{σ2}(F_{σ1}(T_{0}))) = T_{σ3σ2σ1}. |
We see (and this can be shown rigorously by induction) that the triangle
(n) | T_{s1s2...sn} = F_{s1}(F_{s2}(...(F_{sn}(T_{0})...)). |
The sequence of triangles T_{sn}, ..., T_{s2...sn}, T_{s1s2...sn} thus obtained differs from the nested sequence T_{s1}, T_{s1s2}, ..., T_{s1s2...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
References
- 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 F_{A}F_{A}, F_{A}F_{B}, ..., F_{C}F_{C} that consists of 9 contractions each with coefficient 1/4, has exactly the same attractor as the system of three functions F_{A}, F_{B}, F_{C}. For a demonstration, see the applet at the Collage Theorem and IFS page and play with the Iterate button.
|Activities| |Contact| |Front page| |Contents| |Geometry|
Copyright © 1996-2018 Alexander Bogomolny