## The Algorithmic Beauty of Plants

“The idea of form implicitly contains also the history of such a form.”

Notes on Prusinkiewicz and Lindenmayer’s beautiful book, “The Algorithmic Beauty of Plans” (Springer-Verlag, 1990), which is also available online.

## 1 Graphical modeling using L-systems

- Lindenmayer systems, or L-systems, were originally a topological model of plant development, emphasizing the neighborhood relations between plant modules (cells, filaments…).
- Geometry was added later on to make the model more expressive.

### 1.1 Rewriting systems

- Complex objects are composed by successively replaces parts on an initial simple object using a set of
*rewriting rules*or*productions*. Examples are:- von Koch’s rewriting rules for open polygons (snowflake curve)
- Conway’s
*game of life* - Chomsky’s formal grammars

- “The essential difference between Chomsky’s formal grammars and L-systems lies in the method of applying productions.”
- Sequentially in the former, and in parallel in the latter

### 1.2 DOL-systems

- DOL-systems, the simplest class of L-systems, is deterministic and context-free.
*Axiom*is the*initiator*string, and all string rewriting rules are applied simultaneously in each steps. So, given rules (1)`a -> ab`

, and (2)`b -> a`

, the axiom`b`

after two steps becomes`aba`

.

- Formal definition:
- Let be an alphabet, be the set of words, and all non-empty words.
- is a non-empty initial word, called
*axiom*. - be the set of productions.
- is the same as .
- is called
*predecessor*, is called*successor*. - Thus, each character maps to a word. The default production is
*identity*, .

- An OL-system is the triplet .
- An OL-system is deterministic if there is exactly one s.t. .
- A simple example is the simulation of the development of a multi-cellular filament of bacteria
*Anabaena catenula*.

### 1.3 Turtle interpretation of strings

- Graphical representations of L-systems allow modeling more complex plants.
- Turtle interpretation of L-system:
- Current state defined by the triplet , where represent the Cartesian coordinates, and angle is the heading.
- Given the steps size and angle increment , the following actions are possible:
- : move forward a step of size from to , and draw a line.
- : move forward as above without drawing a line.
- : turn left by angle so the current state becomes
- : turn right by angle so the current state becomes

- The following L-system approximates Mandelbrot’s
*quadratic Koch island*:

### 1.4 Synthesis of DOL-systems

*Inference problem*: how can one generate, or discover, the generators for L-systems?- Random modifications don’t yield insight, and in fact may causes a system to die or be stuck in a loop.
- There are no general methods still. Two well-developed heuristics are:
*edge rewriting*and*node rewriting*. “Both approaches rely on capturing the recursive structure of figures and relating it to a tiling of a plane.”

- Edge rewriting:
- Productions operate on units of a figure (edges), substituting the whole figure for each unit.
- A variation of L-systems assumes two types of edges: right (R) and (L) although both correspond to the F command. They are helpful in indicating which side of a line to act on.
- The class of “space-filling, self-avoiding, simple and self-similar” (FASS) curves \ are space-filling i.e. they pass through all points of a square.
- McKenna, in his paper “SquaRecurves, E-Tours, Eddies, and Frenzies: Basic Families of Peano Curves on the Square Grid” [1], that outlines the conditions under which FASS curve generators can be found. Given a figure of order n (i.e. a figure completely tiled by scaled version of itself, aka a “rep-tile”), he proves that:
- “Theorem 1: Generator on order n triangular grids always generate Peano curves that are self-contacting.” Hence, there are no self-avoiding curves in this case.
- “Lemma 1: “There are no bilaterally symmetric self-avoiding Peano curve generator on order n fixed square grids when n is odd”.
- “Theorem 2: Bilaterally symmetric Peano curve generators on order n fixed square grids can never generate self-avoiding approximations, for k > 1” (k is the number of iterations).
- “Even when a generator, consisting of connected line segments, is self-avoiding, this does not necessarily mean that approximations to the Peano curve it generates are self-avoiding.”
- Rotational (unlike bilateral) symmetry allows some generators to mesh in a self-avoiding way.

- The hexagonal and quadratic Gosper curves are examples of FASS:

- Node rewriting:
- Productions operate on units of a figure (nodes), substituting a new figure for each unit.
- Turtle interpretation extension for node rewriting:
- Given subfigure A from a set of subfigures :
- Two contact points: the
*entry point*, and the*exit point* - Two direction vectors:
*entry vector*and the*exit vector*

- Two contact points: the
- Subfigure A is translated and rotated to align with its entry point and direction with the current position and orientation of the turtle.
- Having placed A, the turtle is assigned the resulting exit point and direction.

- Given subfigure A from a set of subfigures :
- The Hilbert curve L-system for subfigures L (f+F) and R (+F):
- When L and R are subfigures reduced to a point, the result is a
*pure curve*.

## References

- The Lighter Side of Mathematics: Proceedings of the Eugene Strens Memorial Conference on Recreational Mathematics and Its History link