Blog

Learn. Make. Repeat.

August 03, 2014

Koch Snowflake and the Thue-Morse Sequence

When you first study recursion, you will invariably run into a "factorial" example. But if you are lucky, you will also run into a far more interesting algorithm - one that draws a fractal geometry construct called the "Koch snowflake". This curve was discovered in 1904 by Swedish mathematician Helge von Koch [1]. Drawing this curve is straightforward, and we will do so using Python turtle graphics. But this curve also has a deeper connection with a mathematical sequence called the Thue-Morse sequence [2], which we will explore in a bit.

Koch Snowflake Construction

The Koch snowflake being a fractal, its structure can be defined in terms of itself. The math involved is shown in the figure below.

Once you know how to draw the line $$A_{1}-P_{1}-P_{2}-P_{3}-B$$ you can draw the curve recursively as follows.


drawKoch(A, B):
   if |AB| < delta:
      draw A-P1-P2-P3-B
   else:
      drawKoch(A, P1)
      drawKoch(P1, P2)
      drawKoch(P2, PP3)
      drawKoch(P3, B)

Now we are ready to draw this with turtle. The output is shown below. (Full code listing at the end of this article.)

Connection with the Thue-Morse Sequence

The Thue-Morse sequence is constructed as follows:

  1. Start with 0.
  2. Append the complement. You get 01.
  3. Repeat the previous step.

Here are the first five terms of the above procedure:

0
01
0110
01101001
0110100110010110

Now, consider the following drawing procedure.

Let \( t(n) \) be the Thue-Morse sequence.

  • If \( t(n) \) is 0, move forward by one unit.
  • If \( t(n) \) is 1, rotate (just change heading, don't move) by 60 degrees anti-clockwise.

Keep repeating the above procedure, and guess what you get? Something astonishingly similar to the Koch snowflake! This idea has been explored by Jun Ma and Judy Holdener, in their 2005 paper "When Thue-Morse Meets Koch" [3]. The paper is not for the faint of heart, and although I am no mathematician, it looks like you need a background in Abstract Algebra and Topology to understand it. But you don't need to know much to draw it. Here is what you get when you put turtle to task to draw the above.

I think this is mind-blowing, and this is why I love mathematics! ;-)

Below is the full source code. Notice that we use a Python generator to create the Thue-Morse sequence.

To see the traditional Koch snowflake, run as:

$python koch.py

To see the Thue-Morse magic in action, run as:

$python koch.py --thue

References

  1. http://en.wikipedia.org/wiki/Koch_snowflake
  2. http://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence
  3. JUN MA AND JUDY HOLDENER, "When Thue-Morse meets Koch," Fractals: Complex Geometry, Patterns, and Scaling in Nature and Society,13(2005) 191-206.