Iterated functions systems (IFS)

A contraction on the plane R2 is a map f:R2 →R2 with the property that there exist a number r such that for any pair of points X, Y in R2 ,

distance(f(X),f(Y))<r. distance(X,Y).

The smallest r with such a property is called the contraction factor

NOTE: We will work with similarities, which are a particular type of contractions.

Iterated functions systems (IFS)

We start with a (compact) set of points P0 and n affine transformations, A1, A2, ..An, which are contractions.

(In our examples, P0 is the initial polyogon or the union of the initial polygons)

Remark: Many of the results could be reproduced in a more general way, starting with any compact set, and a finite number of contractions.

The “recipe”: We define inductively

P1=A1(P0) U A2(P0) U .. U An(P0)

P2=A1(P1) U A2(P1) U .. U An(P1)

P3=A1(P2) U A2(P2) U .. U An(P2)

...

n. Pn_=A1(P(n-1)) U A2(P(n-1)) U .. U An(P(n-1))

Theorem:

The sequence P0, P1, P2, P3... converges to a unique shape P (of finite extent) invariant under the applications of A1, A2, . , An. In symbols,

P=A1(P) U A2(P) U ... An(P).

This shape P is called the attractor of the IFS {A1, A2.. An}

When the transformations A1, A2.. An are all affine transformations, they the list of parameters

[a1, b1, c1, d1, e1, f1] (param. of A1)

[a2, b2, c2, d2, e2, f2] (param. of A2)

.

.

[an, bn, cn, dn, en, fn] (param. of An)

are called the IFS parameters of the attractor.

Definition

For a self-similar shape made of N copies of itself, each scaled by an affine contraction of contraction factor r, the similarity dimension is

log(N)/log(1/r)

Propositon:

Let l1, l2,.. ln be a list of IFS parameters. Suppose they are all correspond to contractions of ratio r.

Moreover, assume that there is a polygon P such that the union of the images of P by each of the transformations of the list is “just touching”.

Then the similarity dimension of the attractor of the IFS is ln(n)/ln(1/r).

NOTE: “Just touching” means that the sets intersect only in the boundary.

2006-05-04T11:19:42