# Playing with iterated function systems

After Colin Carroll posted several fractal experiments with Matlab, I decided to do something of the sort. One difference is that I use Scilab, an open-source alternative to Matlab.

The first experiment: drawing the Sierpinski carpet using the Chaos Game. Namely, given a finite family of strict contractions $f_1,\dots,f_r\colon \mathbb R^2\to \mathbb R^2$ and an initial point $p_0$, plot the sequence $p_{n+1}=f_{j_n}(p_n)$, where $j_n \in \{1,\dots,r\}$ is chosen randomly at each step. To simplify matters, let $f_j$ be the similarity transformation with scaling factor $s\in (0,1)$ and the fixed point $v_j$.

A canonical example is: $v_1,v_2,v_3$ are the vertices of equilateral triangle, $s=1/2$. This produces the fractal known as the Sierpinski gasket. For a different example, set $s=1/3$ and let $v_1,\dots,v_8$ be the vertices of square together with midpoints of its sides. The resulting fractal is known as the Sierpinski carpet.

This image was obtained by calling the scilab function given below as Scarpet(1/3, 100000). The function is essentially a translation of Colin’s code to scilab. Caution: if you copy and paste this code, watch out for line breaks and encoding of quote marks.

function Scarpet(scale,steps)
b=1-scale;
x = [1,0,-1,-1,-1,0,1,1];
y = [1,1,1,0,-1,-1,-1,0];
sides=length(x);
point = zeros(steps,2);
vert = grand(1,steps,'uin',1,sides);
for j = 2:steps
point(j,:) = scale*point(j-1,:) + b*[x(vert(j)),y(vert(j))];
end
plot(point(:,1),point(:,2),'linestyle','none','markstyle','.','marksize',1);
endfunction

Regardless of the choice of initial point $p_0$, the set of cluster points of the sequence $(p_n)$ is exactly the invariant set $K$, namely the unique nonempty compact set such that $K=\bigcup_{j=1}^r f_j(K)$. This is proved, for example, in the book Integral, Probability, and Fractal Measures by Gerald Edgar.

The scaling factor $s=1/3$ for the carpet is chosen so that the images of the original square under the eight similarities touch, but do not overlap. With a smaller factor the fractal looks like dust (a totally disconnected set), while with $s\ge 1/2$ it becomes a solid square. The intermediate range $1/3 is tricky: I think that $K$ has measure zero, but can’t even prove that it’s nowhere dense.

It’s also possible to draw $K$ in the opposite way, by removing points rather than adding them. To this end, let $P$ be the convex hull of the set $\{v_1,\dots,v_r\}$; that is, a solid convex polygon. It’s not hard to see that $K\subset P$. Therefore, $\bigcup_{j=1}^r f_j(K)\subset \bigcup_{j=1}^r f_j(P)$, but since the set on the left is $K$ itself, we get $K\subset \bigcup_{j=1}^r f_j(P)$. By induction, $K=\bigcap_{n=1}^{\infty} P_n$ where $P_0=P$ and $P_{n+1}=\bigcup_{j=1}^r f_j(P_n)$.

The above example is ifs(3,3/5,11), calling the Scilab code below.

function ifs(sides,scale,steps)
b=1-scale; t=2*%pi*(1:sides)/sides; x=cos(t); y=sin(t);
xpols=x'; ypols=y';
for j=2:steps
xpols=scale*xpols; ypols=scale*ypols;
xpolsnew=[]; ypolsnew=[];
for k=1:sides
xpolsnew=[xpolsnew xpols+b*x(k)*ones(xpols)];
ypolsnew=[ypolsnew ypols+b*y(k)*ones(ypols)];
end
xpols=xpolsnew; ypols=ypolsnew;
end
a=gca(); a.data_bounds=[-1,-1;1,1];
[m,n]=size(xpols);
xfpolys(xpols,ypols,ones(n,1))
endfunction

The final example is an “upper bound” for the fat pentagonal fractal that Colin created with the Chaos Game: the points $v_1,\dots,v_5$ are the vertices of regular pentagon, and $s=1/2$. The function was called as ifs(5,1/2,8). Again, I think that the invariant set has measure zero, but can’t even prove that the interior is empty. (Or find a reference where this is already done.)