Collage theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 of the theorem[edit]

Let \mathbb{X} be a complete metric space. Suppose L is a nonempty, compact subset of \mathbb{X} 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, (The contractivity factor of the IFS is the maximum of the contractivity factors of the maps w_i.) Suppose

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, for all nonempty, compact subsets L of \mathbb{X}.

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[edit]


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

External links[edit]