Posts Tagged ‘Recursion’

Following a discussion on Reasonable Deviations. I was prompted to write on this.


The above is an illustration on the generation of the Sierpinski Gasket. For simplicity we assume that the area of the initial triangle is 1. We split this triangle into four triangles by joining the mid-points of the sides of the triangle. These smaller triangles as shown in figure 2 have equal areas. We then remove the middle triangle. We adopt the convention that we will only remove the middle triangle and not a triangle at the edge.

In each of the three remaining triangles we repeat the process and remove the middle triangles. This is where self-symmetry comes in. If we pretend to see only one of the three small triangles then we are actually doing the same thing as we did to the original triangle. Albeit on a smaller scale. The above figure shows the third and fourth iterates of the original triangle. This process repeated ad infinitum gives rise to the Sierpinski gasket.

The L-System representation of the process is:

variables : A B

constants : + −

start : A

rules : (A → B−A−B),(B → A+B+A)

angle : 60°

Anyway, now what is interesting about this figure is its area and the perimeter.

Continuing with our earlier assumption, suppose the initial triangle had an area

A0= 1;

Now in the first iteration we remove one of the four equal areas in that triangle and keeping the other three that remain.

Therefore the total area of the first iterate will be equal to

A1 = (3/4) x 1;

Similarly in the second iteration, we repeat the process as I have already noted above. Thus,

A2 = (3/4)(3/4) x 1;

For n iterations the area will be given by:

An = (3/4)n x 1;

Now if n is arbitrarily large then the area, it would follow will be ZERO.

Now finding out the perimeter is a similar exercise. The length of the boundary of the nth iterate of the original triangle is the total length of the boundaries of all the shaded small triangles in the nth iterate. It can be shown that this gets arbitrarily large as n gets arbitrarily large. Therefore we conclude that a Sierpinski gasket has infinite perimeter!

And that it has zero area inside and infinite perimeter.

This is against the Koch Snowflake, which is a figure having a finite area inside an infinite perimeter. This goes against the way we think and according to geometric intuition that we have. But it actually is characteristic of many shpaes in nature. For example (i really like this example :D ) if we take all the arteries, veins and capillaries in the human body, then they occupy a relative small fraction of the body. Yet if we were able to lay them out end to end, we would find that the total length would come to over 60000 kilometres. This example i am quoting from an article i had copied years ago.


Related Article:

Lindenmayer systems and Fractals

Onionesque Reality Home >>

Read Full Post »

L-systems are very simple and elegant grammars (a set of rules and symbols) originally developed by biologist Aristid Lindenmayer to describe the growth of plants and trees.


These as we can see can lead to very beautiful figures as above!

Photo Credit.

The Lindenmayer system is recursive in nature which leads to self-similarity and hence fractal like structures. Plant models and natural-looking organic forms are similarly easy to define, as by increasing the recursion level the form slowly ‘grows’ and becomes more complex.

The components of a L-system are:

A) The alphabet, which is a finite set V of formal symbols or characters, generally they are taken to be letters A,B,C etc. These are the variables as they can be replaced. A set of symbols which will remain fixed are constants. These may be represented as another finite set.

B) The start, axiom or initiator ω, it basically is a string of symbols from V. If suppose V = {a,b,c} then ω can be aabc, abcc, abcab etc. There are many possibilities. This defines the initial state of the system.

C) Production rules, P that define how a variable can be replaced by a combination of variables and constants.

The rules of the L-system grammar are applied iteratively starting from the initial state. As many rules as possible are applied simultaneously, per iteration. This is the distinguishing feature of a L-system from a language.

There are many examples of the same that lead to very beautiful structures!

Some are:

A) Cantor Dust:

variables : A B

constants : none

start : A {starting character string}

rules : (A → ABA), (B → BBB)

Let A mean “draw forward” and B mean “move forward”.

Put in a different manner. We could say that a cantor dust fractal may be reconstructed using string rewriting using an initial cell {1} and then iterating the below rules.

{0->[0 0 0; 0 0 0; 0 0 0],1->[1 0 1; 0 0 0; 1 0 1]}.

Thus we would get the fractal as :


B) Fractal Tree:

variables : X F

constants : + −

start : X

rules : (X → F-[[X]+X]+F[+FX]-X),(F → FF)

angle : 25°

Here, F means “draw forward”, – means “turn left 25º”, and + means “turn right 25º”. X does not correspond to any drawing action and is used to control the evolution of the curve. For n=6 the following figure may be generated.


C) The Sierpinski Triangle:
variables : A B

constants : + −

start : A

rules : (A → B−A−B),(B → A+B+A)

angle : 60°

Here, A and B mean both “draw forward”, + means “turn left by angle”, and − means “turn right by angle”. The angle changes sign at each iteration so that the base of the triangular shapes are always in the bottom (they would be in the top and bottom, alternatively, otherwise).

Evolution for n = 2, n = 4, n = 6, n = 9

Other curves include the famous Koch Curve, Dragon Curve, Penrose Tilings etc.

Good places to do initial research on L-Systems:

1. Wikipedia

2. Fractinct L-system True Fractals, A tutorial by William Mcworter.

3. Fractals and Cellular Automata. by Daniel Shiffman.

4. Fractals and Recursion in the Nature of Code.

I would try to follow these initial posts on fractals with applications in RFID and in other smart antenna applications.

Also check out this voronoi fractal on this post. Credits to the image given in the original post.


Read Full Post »