Collage theorem

In mathematics, the collage theorem describes a constructive technique for approximating sets of points in Euclidean space (typically images) to any degree of precision with the attractor of an iterated function system. It is typically used in fractal compression.

Statement of the theorem

Let $\mathbb {X}$ be a complete metric space. Let $L\in {\mathcal {H}}(\mathbb {X} )$ be given, and let $\epsilon \geq 0$ be given. Choose an Iterated function system (IFS) $\{\mathbb {X} ;w_{1},w_{2},\dots ,w_{N}\}$ with contractivity factor $0\leq s<1$, so that

$h\left(L,\bigcup _{n=1}^{N}w_{n}(L)\right)\leq \varepsilon ,$

where $h(d)$ is the Hausdorff metric. Then

$h(L,A)\leq {\frac {\varepsilon }{1-s}}$

where A is the attractor of the IFS. Equivalently,

$h(L,A)\leq (1-s)^{-1}h\left(L,\cup _{n=1}^{N}w_{n}(L)\right)\quad {\text{for all }}L\in {\mathcal {H}}(\mathbb {X} ).$

See also

• Michael Barnsley
• Iterated function system

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