Collage theorem
Encyclopedia
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
.
be a complete metric space. Let 
be given, and let 
be given. Choose an iterated function system
(IFS)
with contractivity factor 
, so that
where
is the Hausdorff metric. Then
where A is the attractor of the IFS.
Iterated function system
In mathematics, iterated function systems or IFSs are a method of constructing fractals; the resulting constructions are always self-similar....
whose attractor
Attractor
An attractor is a set towards which a dynamical system evolves over time. That is, points that get close enough to the attractor remain close even if slightly disturbed...
is close, relative to the Hausdorff metric, to a given set. The IFS described is composed of contractions
Contraction mapping
In mathematics, a contraction mapping, or contraction, on a metric space is a function f from M to itself, with the property that there is some nonnegative real number k...
whose images, as a collage or union
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
when mapping the given set, are arbitrarily close to the given set. It is typically used in fractal compression
Fractal compression
Fractal compression is a lossy compression method for digital images, based on fractals. The method is best suited for textures and natural images, relying on the fact that parts of an image often resemble other parts of the same image...
.
Statement of the theorem
Let be a complete metric space. Let be given, and let be given. Choose an iterated function systemIterated function system
In mathematics, iterated function systems or IFSs are a method of constructing fractals; the resulting constructions are always self-similar....
(IFS)
with contractivity factor , so thatwhere
is the Hausdorff metric. Thenwhere A is the attractor of the IFS.
External links
- A description of the collage theorem and interactive Java applet at cut-the-knotCut-the-knotCut-the-knot is a free, advertisement-funded educational website maintained by Alexander Bogomolny and devoted to popular exposition of many topics in mathematics. The site has won more than 20 awards from scientific and educational publications, including a Scientific American Web Award in 2003,...
. - Notes on designing IFSs to approximate real images.
- Expository Paper on Fractals and Collage theorem