Sketchy Polytopes

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:
Hexagonal Gosper curveQuadratic Gosper curve
  • 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
      • 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.
    • 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.


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