Collage theorem

In mathematics, the collage theorem characterises an iterated function system whose attractor is close, relative to the Hausdorff metric, to a given set. The IFS described is composed of contractions whose images, as a collage or union when mapping the given set, are arbitrarily close to the given set. It is typically used in fractal compression.

Statement

Let $\mathbb{𝕏}$ be a complete metric space. Suppose $L$ is a nonempty, compact subset of $\mathbb{𝕏}$ and let $ϵ>0$ be given. Choose an iterated function system (IFS) $\{\mathbb{𝕏};w_1,w_2,\dots ,w_N\}$ with contractivity factor $s,$ where $0\le s<1$ (the contractivity factor $s$ of the IFS is the maximum of the contractivity factors of the maps $w_i$). Suppose

$h(L,\bigcup _{n=1}^N{w}_n(L))\le \epsilon ,$

where $h(\cdot ,\cdot )$ is the Hausdorff metric. Then

$h(L,A)\le \frac{\epsilon }{1-s}$

where A is the attractor of the IFS. Equivalently,

$h(L,A)\le (1-s{)}^{-1}h(L,\underset{n=1}{\overset{N}{\cup }}{w}_n(L))$, for all nonempty, compact subsets L of $\mathbb{𝕏}$.

Informally, If $L$ is close to being stabilized by the IFS, then $L$ is also close to being the attractor of the IFS.

See also

• Michael Barnsley
• Barnsley fern

References

• Barnsley, Michael. (1988). Fractals Everywhere. Academic Press, Inc. ISBN 0-12-079062-9.

External links

• A description of the collage theorem and interactive Java applet at cut-the-knot.
• Notes on designing IFSs to approximate real images.
• Expository Paper on Fractals and Collage theorem