Curves and L-systems

The picture above shows an approximation to the Gosper curve, which was discovered by Bill Gosper in 1973. The Gosper curve is a space-filling curve, which means that it converges to a curve that completely fills in the interior of a shape. The shape in question (shown below) is called the Gosper island. Despite having a fractal boundary, the Gosper island has a property called “rep-7”, which means that it can be split up into 7 identical smaller copies of itself. This gives a way to tile the plane by using copies of the Gosper island.

Shapes that have the property rep-n for some value of n are collectively known as rep-tiles. There are many examples of rep-tiles, such as those shown in the picture below. You may like to see if you can find the two “fish”, and guess which of the shapes is called the “sphinx”.

Fractals like the Gosper curve can often be constructed using L-systems. The “L” stands for Lindenmayer, after the theoretical biologist Aristid Lindenmayer, who introduced them in 1968. An L-system consists of an alphabet, an initial state, and a set of production rules. Lindenmayer’s original system was designed to model the growth of algae. It has an alphabet of two letters, {A, B}, an initial state of A, and two production rules: (A ↦ AB) and (B ↦ A). The production rules indicate that at each iteration of the procedure, we replace each occurrence of “A” by “AB”, and each occurrence of “B” by “A”. Iterating this procedure, we obtain the sequence A, AB, ABA, ABAAB, ABAABABA, ABAABABAABAAB, and so on. This sequence converges to an infinitely long word called the Fibonacci word. If we take any of the words in this sequence, for example ABAABABAABAAB, we find that the number of As (eight in this case), the number of Bs (five), and the total number of letters (thirteen) are all Fibonacci numbers. (The Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, … have the property that each number beyond the first two is the sum of the previous two numbers.) 

Other L-systems can be used to model the growth of plants, and to generate fairly realistic pictures, like the ones above.

The L-system for the Gosper curve has an alphabet consisting of four symbols: {A, B, +, –}. The initial state is A, and there are two production rules: (A ↦ A – B – – B + A + + A A + B –) and (B ↦ + A – B B – – B – A + + A + B).  The resulting strings should be thought of as instructions to a graphics turtle that is drawing the Gosper curve: the letters “A” and “B” each mean “move forward”, “+” means “turn left 60°”, and “–” means “turn right 60°”.  

The terdragon curve is another curve that can be constructed with an L-system. (The curve is a triangular version of another curve called the dragon curve, which is presumably where the name comes from.) The terdragon curve covers the plane in the sense that it eventually visits every edge in a triangular lattice. The L-system in this case has an alphabet of three symbols, {F, +, –}. The initial state is F, and there is a single production rule: (F ↦ F – F + F). The symbol “F” means “move forward”, “–” means “turn right 120°”, and “+” means “turn left 120°”. The first six steps of the iteration are shown in the picture above. The picture below is a 3D sculpture showing a developing terdragon curve.

I found about the terdragon curve from the recent paper Coverings of the plane by self-avoiding curves which satisfy the local isomorphism property by Francis Oger. Oger considers a generalization of the terdragon curve in which there are two versions of the production rule, (F ↦ F + F – F) and (F ↦ F – F + F), and these can be applied in an arbitrary order. The type of such a curve is the (infinite) sequence of production rules used to construct it. Oger proves that different sequences of production rules give rise to different curves, in a sense made precise in the paper, and that if Λ is any sequence of production rules, then it is possible to cover the plane in a unique way with copies of curves of type Λ.

---

Picture credits and relevant links

The picture of the terdragon curve comes from the paper Developing fractal curves by Geoffrey Irving and Henry Segerman. The 3D sculpture shown is by Henry Segerman and was exhibited in the SFO Museum. The paper by Irving and Segerman contains many other striking images.

The picture of the Gosper curve is by Arbol01 and Blotwell. The pictures of the Gosper island are by Inductiveload. All these pictures appear on Wikipedia.

The rep-tile picture is by MagistraMundi and appears on Wikipedia.

The artificial plant images are by Solkoll and appear on the Wikipedia page on L-systems.

Wikipedia has a page about the Fibonacci word.

Jeffrey Ventrella’s YouTube video Growing the Ter-Dragon shows the first few steps of the terdragon curve as an animation.