Collage theorem explained

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

X be a complete metric space. Suppose L is a nonempty, compact subset of X and let \epsilon > 0 be given. Choose an iterated function system (IFS) \{ X ; w _{1,} w _{2,} ... , w _{N\}} with contractivity factor s, where 0 \leq s < 1 (the contractivity factor s of the IFS is the maximum of the contractivity factors of the maps w _{i} ). Supposeh\left( L, c up ^{N} _{n =1} w _{n} (L) \right) \leq \varepsilon,

where

h( ⋅ , ⋅ ) is the Hausdorff metric. Thenh(L,A) \leq (\varepsilon)/(1- s)

where A is the attractor of the IFS. Equivalently,

h(L,A) \leq ( 1- s) ^{-1} h\left(L,\cup ^{N} _{n =1} w _{n(L)\right)} , for all nonempty, compact subsets L of 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

• Michael Barnsley
• Barnsley fern

References

• Book: Barnsley, Michael. . Fractals Everywhere . registration . 1988 . Academic Press, Inc. . 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