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 [math]\displaystyle{ \mathbb{X} }[/math] be a complete metric space. Suppose [math]\displaystyle{ L }[/math] is a nonempty, compact subset of [math]\displaystyle{ \mathbb{X} }[/math] and let [math]\displaystyle{ \epsilon \gt 0 }[/math] be given. Choose an iterated function system (IFS) [math]\displaystyle{ \{ \mathbb{X} ; w_1, w_2, \dots, w_N\} }[/math] with contractivity factor [math]\displaystyle{ s, }[/math] where [math]\displaystyle{ 0 \leq s \lt 1 }[/math] (the contractivity factor [math]\displaystyle{ s }[/math] of the IFS is the maximum of the contractivity factors of the maps [math]\displaystyle{ w_i }[/math]). Suppose
- [math]\displaystyle{ h\left( L, \bigcup_{n=1}^N w_n (L) \right) \leq \varepsilon, }[/math]
where [math]\displaystyle{ h(\cdot,\cdot) }[/math] is the Hausdorff metric. Then
- [math]\displaystyle{ h(L,A) \leq \frac{\varepsilon}{1-s} }[/math]
where A is the attractor of the IFS. Equivalently,
- [math]\displaystyle{ h(L,A) \leq (1-s)^{-1} h\left(L,\cup_{n=1}^N w_n(L)\right) \quad }[/math], for all nonempty, compact subsets L of [math]\displaystyle{ \mathbb{X} }[/math].
Informally, If [math]\displaystyle{ L }[/math] is close to being stabilized by the IFS, then [math]\displaystyle{ L }[/math] is also close to being the attractor of the IFS.
See also
References
- Barnsley, Michael. (1988). Fractals Everywhere. Academic Press, Inc.. ISBN 0-12-079062-9. https://archive.org/details/fractalseverywhe0000barn.
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
 |  |
