## Cut The Knot!An interactive column using Java applets
by Alex Bogomolny |

# The Collage Theorem

March 1998

That the terms of mathematics may be confusing is often claimed even by professional mathematicians. As an example, spaces and sets contain points. Yet there are spaces whose "points" are themselves sets. Functions map points to points but also comprise (function) spaces where each is considered an indivisible one. From the mathematician's view *point*, the advantage of abstracting a point from its diverse incarnations is in the achieved generality. A statement is proven only once and then applied repeatedly in various disguises.

Case in *point* - contraction mappings and the related convergence theorems. Contraction mappings are defined on metric spaces by the property that they decrease the distance between points. In complete spaces, any contraction mapping has a unique fixed point that can be found by (necessarily) convergent iterations. Convergence estimates relate proximity of iterations to the selection of the initial point. These general estimates apply as much to the solutions of integral and differential equations, matrices, and more general operators. Iterated Function Systems (IFSs) is another rewarding topic that capitalizes on the general theory.

An **Iterated Function System** is a finite collection of contractions F_{i}: XX defined on a metric space X. Each extends to a mapping (different but denoted by the same letter) F_{i}: H(X)H(X), where H(X) is the space whose points are nonempty compact subsets of X. When endowed with the Hausdorff metric, H(X) is complete if so was X. In addition, contractions F_{i}XX remain contractions as mappings of H(X). Together, {F_{i}} define another contraction F: H(X)H(X), by the following formula: for every AH(X), F(A) = ∪F_{i}(A). From the general theory, for a complete metric space X, F has a fixed point A_{F}: F(A_{F}) = A_{F}, that can be reached by successive approximations from any starting location. Fixed points of IFSs are variously called attractors or invariant sets.

Two problems arise. One is to find the fixed point of a given IFS. The other is the inverse of the first: for a given set AH(X), find an IFS {F_{i}} that has A as its fixed point. In the general framework, the first problem is solved by what is known as the *deterministic* algorithm. Start with a set A_{0}∈H(X) and compute successively _{k} = ∪F_{i}(A_{k-1}) = F(A_{k-1}),_{k}) converges to the fixed point A_{F} of {F_{i}} as k. The mathematics of the second, *random iteration* algorithm, is more complex but implementation is more straightforward. Assign positive frequencies p_{i} to the mappings F_{i}. Start with an arbitrary point x_{0}∈X. At every step k+1, select x_{k+1} from the set {F_{i}(x_{k})}. F_{j}(x_{k}) is selected with the probability p_{j} /p_{i}. In a sense that is made precise in [Barnsley], the sequence {x_{k}} converges to A_{F}. In practical terms, to depict an approximation of A_{F} on a computer, the points of the sequence are displayed starting with a reasonably large index. The numbers {p_{i}} have no effect on the fixed point A_{F} but influence significantly the rendering of its approximations.

The inverse problem is solved approximately by the **Collage Theorem**. In the words of M. Barnsley, the theorem tells us that to find an IFS whose attractor is "close to" or "looks like" a given set, one must endeavor to find a set of transformations - contraction mappings on a suitable set within which the given set lies - such that the union, or **collage**, of the images of the given set under transformations is near to the given set.

The applet below was inspired by Barnsley's celebrated depiction of the Black Spleenwort fern. Three parallelograms almost covering the fourth and bigger one looked as naturally associated with the fern as each of its smaller branches. There was another parallelogram - a smallish and a *degenerate* one - that is often omitted in reproductions.

Parallelograms lead to affine transformations; for the latter map parallel lines onto parallel lines. Affine transformations can be uniquely determined from images of any three distinct points - three consecutive vertices of a parallelogram in particular.

The applet consists of two parts. The first is the display area with several controls. First of all, there are several predefined IFSs to select from. For a given IFS, **Start** starts the iterations of the random iteration algorithm; **Stop** stops them. The applet attempts to optimally exploit the visual estate. The algorithm is heuristic and sometimes is off by an iteration or two. If needed, **Shrink** the emerging image and **Clear** the area. Often, the component sets F_{i}(A_{F}) intersect only over sets of lower dimension. In such a case, the **Color** option, that randomly assigns a color to each F_{i}(A_{F}), may create an unusually beautiful effect. **Reset** restores the original state of the IFS.

A simple observation that two IFSs, {F_{i}} and {F_{i}F_{j}} have exactly the same fixed point, leads to a representation of A_{F} as a union of a growing number of sets. To see how this works use the **Iterate** button.

When the **Transforms** box is checked the second portion of the applet (Affine Basis Manipulator) appears in a separate window. This is the place to apply the Collage theorem. The **Which** buttons designate one of the parallelograms to manipulate. The selected parallelogram is displayed in red-blue-white colors whereas all others are entirely gray. Red and blue edges can be changed independently or the whole structure can rotate around their common vertex. The first parallelogram is the most basic. All others are considered its images under affine transformations. Please bear in mind that the number of transformations is, therefore, 1 less than the number of parallelograms.

Apply the **Iterate** button with the Affine Basis Manipulator on. The regions will multiply and become smaller. To boot, this is a demonstration of the deterministic algorithm with the first parallelogram as the starting point.

Each of the parallelograms is an image of the unit square (0,0)-(1,1) under an affine mapping (x,y)(ax+by+e, cx+dy+f). Two rows of edit controls give you a direct access to the values of a,b,e (the first row) and c,d,f (the second row.) Beware: the coordinate system is the usual one for computer graphics. Y axis grows downwards.

What if applet does not run? |

Using parallelograms to define affine transformations may be a mixed blessing. For one, parallelograms may not resemble the resulting sets in the least. Even overlapping parallelograms may sometimes lead to a perfect tiling of the resulting set (see Sierpinski 2).
Further, two parallelograms can be mapped onto each other in 8 different ways. (Pick a vertex as the origin and the order of the two adjacent vertices.) So, while a parallelogram remains the same geometric region, it can be associated with several transformations. Each such selection leads to a different IFS with a different fixed point. Bring up the second window and compare the Twindragon, Dragon, Monster, and Surprise IFSs. They all start with the same regions. But **Iterate** and watch the deterministic algorithm at work.

### References

- M. Barnsley,
*Fractals Everywhere*, Academic Press, 1988 *Chaos and Fractals*, R. L. Devaney and L. Keen (eds), AMS, 1989- D. M. Davis,
*The Nature and Power of Mathematics*, Princeton University Press, 1993 - P. Hilton, D. Holton, J. Pederson,
*Mathematical Reflections*, Springer Verlag, 1997 *The Science of Fractal Images*, H.-O.Peitgen and D.Daupe (eds), Springer-Verlag, 1988

### On the Web

- Dot Patterns and Sierpinski Gasket
- Sierpinski Gasket By Common Trema Removal
- Sierpinski Gasket Via Chaos Game
- Sierpinski Gasket By Trema Removal
- Collage Theorem And Iterated Function Systems
- The Chaos Game: Address Space vs IFS
- Sierpinski Gasket and Tower of Hanoi
- Barycentric Coordinates
- Similarity Dimension
- Iterations and the Mandelbrot Set
- Mandelbrot and Julia sets
- Emergence of Chaos

|Contact| |Front page| |Contents| |Geometry| |CTK|

Copyright © 1996-2018 Alexander Bogomolny