August 2nd 2009

The Fibonacci fractal

The Fibonacci fractal is an interesting fractal bearing many relations to the Fibonacci sequence. It was brought to my attention by Alexis Monnerot-Dumaine (who wrote the above article). I've explained in this post how the (boundary of the) Koch snowflake appeared when piling a pattern of hexagons. The Fibonacci fractal can be constructed through a similar "riddle" algorithm, by removing squares (see the article, section 6.3).

One major difference, however, is that the squares to be removed form a pattern which changes at each scale, contrary to the case of the Koch snowflake, where the hexagons belong to rescaled copies of a regular hexagonal tiling. This changing pattern can be described quite simply through recursion: given any already removed square, remove eight smaller squares regularly arranged around it. It was quite challenging to fit a changing pattern into the framework of my algorithms, which until now only piled the same pattern at each scale. I do think this idea opens up a lot of new possibilities, that I'll probably come back to in a forthcoming post. The evolving square pattern is described by the pictures below.

The first set of squares to be removed

The second set of squares to be removed. There are eight of them around each of the first generation squares.

The third generation of squares, arranged in a similar way around the second generation squares. Note that some of these squares overlap squares of the first generation. If we were considering a mere riddle algorithm, this would be irrelevant. However we are in fact piling characteristic functions (which, say, vanish outside squares and have a constant finite value inside each square), so the superimposed squares show up in the picture.

Here is the pattern appearing after piling a reasonable number of square generations. Compare it with the pictures of the Fibonacci fractal in the pdf file.

Inside each square, the overlapping squares combine to form a cute fractal curve, bearing some resemblance with the Koch snowflake.

Still, I find the pictures above a little bit boring, because they contain large flat areas without any structure. (They do not satisfy the definition of an algorithmic world.) This comes from the fact that the sucessive patterns formed by the higher generation squares do not cover the plane. But there is a remedy for this: just mix each of these square patterns with another pattern! In the picture below, they were mixed with the Perlin noise function, what gives the cloudy texture.

20090730-1

I find fascinating the fact that each square is regularly surrounded by eight smaller squares, creating a kind of recursive mandala. With some imagination, one could build a whole cosmogony on this fact... Click on the picture above for a zoomable image.