Iterated Function System (IFS)

Iterated Function System

Let $(X,d)$ be a complete metric space, $\mathcal{H}(X)$ be the set of non-empty compact subset of $X$, an iterated function system (IFS) on $(X,d)$ is a finite collection $f_1,\cdots ,f_k$ of contractions on $X$, i.e. $d_x(f_i(x),f_i(y))\le c_i{d}_x(x,y)0\le c_i<1$

Hutchinson Operator of IFS

The Hutchinson Operator of IFS is the function $\tilde{S}:\mathcal{H}(X)\to \mathcal{H}(X)\text{defined by}\tilde{S}(A)=f_1(A)\cup f_2(A)\cdots \cup f_k(A)$.

Attractor of IFS

An $\tilde{S}$-invariant set (or an attractor of the IFS) is a point $A\in \mathcal{H}(X)$ that $\tilde{S}(A)=A$.

Hausdorff Distance

We define a metric on $\mathcal{H}(X)$, for $(X,d)$ a metric space. $d(a,B)={\inf }_{b\in B}\{d(a,b)\mid b\in B\},$ $d(A,B)={\sup }_{a\in A}\{d(a,B)\},$ $h(A,B)=\max \{d(A,B),d(B,A)\}.$ $h$ is a metric on $\mathcal{H}(X)$.

Theorem

If $(X,d)$ is a complete metric space, then $(\mathcal{H}(X),h)$ is also a complete metric space.

Theorem

For an IFS, the corresponding Hutchinson Operator $\tilde{S}:\mathcal{H}(X)\to \mathcal{H}(X)$ is a contraction on $(\mathcal{H}(X),h)$, so with complete $X$, there is a unique non-empty compact $A\subset X$ s.t. $\tilde{S}(A)=f_1(A)\cup f_2(A)\cdots \cup f_k(A)=A$

Totally Dis connected IFS

Let an IFS, $({\mathbb{R}}^m,f_1,\dots f_k)$, we call an infinite word$\sigma =({\sigma }_1,{\sigma }_2,\dots {\sigma }_k,\dots )$ of $\{f_i\}$ an address for $a$ if $x,{\sigma }_1(x),{\sigma }_2{\sigma }_1(x),\dots$ a Cauchy sequence converges to $a$ for $x\in {\mathbb{R}}^m$. If every $a\in A$ has a unique address for the IFS, we call it totally disconnected. Equivalently, the condition is the same as $f_i(A)\cap f_j(A)=\varnothing \forall ,i\ne j.$

Just Touching

Let an IFS, $({\mathbb{R}}^m,f_1,\dots f_k)$, with attractor $A$, we say it’s just touching if there is a non-empty open subset $U\subset A$ such that $f_i(U)\cap f_j(U)=\varnothing \forall i\ne j,f_i(U)\subset U\forall i$

College Theorem

Suppose $({\mathbb{R}}^n,S_1,\dots ,S_k)$ is an Iterated Function System (IFS) of contractions such that for all $i=1,\dots ,k$: $d(S_i(x),S_i(y))\le cd(x,y)$ (where $c=\max \{c_i\}$ is the maximum contraction factor). Let $F$ be the attractor of this IFS. Then for any set $E\in \mathcal{H}({\mathbb{R}}^n)$, the distance between $E$ and the attractor $F$ is bounded by: $d(E,F)\le d\left(E,{\bigcup }_{i=1}^k{S}_i(E)\right)\cdot \frac{1}{1-c}$

Corollary

Given a target set $E$ and a value $\delta >0$, there exists an IFS $({\mathbb{R}}^n,S_1,\dots ,S_k)$ with an attractor $F$ such that: $d(E,F)<\delta$