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 {\displaystyle \mathbb {X} } be a complete metric space. Suppose L {\displaystyle L} is a nonempty, compact subset of X {\displaystyle \mathbb {X} } and let ϵ > 0 {\displaystyle \epsilon >0} be given. Choose an iterated function system (IFS) { X ; w 1 , w 2 , … , w N } {\displaystyle \{\mathbb {X} ;w_{1},w_{2},\dots ,w_{N}\}} with contractivity factor s , {\displaystyle s,} where 0 ≤ s < 1 {\displaystyle 0\leq s<1} (the contractivity factor s {\displaystyle s} of the IFS is the maximum of the contractivity factors of the maps w i {\displaystyle w_{i}} ). Suppose
h ( L , ⋃ n = 1 N w n ( L ) ) ≤ ε , {\displaystyle h\left(L,\bigcup _{n=1}^{N}w_{n}(L)\right)\leq \varepsilon ,}where h ( ⋅ , ⋅ ) {\displaystyle h(\cdot ,\cdot )} is the Hausdorff metric. Then
h ( L , A ) ≤ ε 1 − s {\displaystyle h(L,A)\leq {\frac {\varepsilon }{1-s}}}where A is the attractor of the IFS. Equivalently,
h ( L , A ) ≤ ( 1 − s ) − 1 h ( L , ∪ n = 1 N w n ( L ) ) {\displaystyle 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 X {\displaystyle \mathbb {X} } .Informally, If L {\displaystyle L} is close to being stabilized by the IFS, then L {\displaystyle L} is also close to being the attractor of the IFS.
See also
- Barnsley, Michael. (1988). Fractals Everywhere. Academic Press, Inc. ISBN 0-12-079062-9.