Collage theorem

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 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 \epsilon$,

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

$h(L,A)\leq \epsilon /(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)$ for all $L\in {\mathcal {H}}(\mathbb {X} )$

References

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

See also

• Michael Barnsley
• Iterated Function System

External links

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