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 $V$ be an alphabet, $V*$ be the set of words, and $V+$ all non-empty words.
• $w \in V+$ is a non-empty initial word, called axiom.
• $P \subset V x V*$ be the set of productions.
• $(a, x) \in P$ is the same as $a \rightarrow x$.
• $a$ is called predecessor, $x$ is called successor.
• Thus, each character maps to a word. The default production is identity, $a \rightarrow a$.
• An OL-system is the triplet $G = (V, w, P)$.
• An OL-system is deterministic if there is exactly one $x \in V*$ s.t. $a \rightarrow x$.
• 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 $(x, y, \alpha)$, where $(x, y)$ represent the Cartesian coordinates, and angle $\alpha$ is the heading.
• Given the steps size $d$ and angle increment $\delta$, the following actions are possible:
• $F$: move forward a step of size $d$ from $(x, y)$ to $(x + dcos(\alpha)), y + dsin(\alpha)$, and draw a line.
• $f$: move forward as above without drawing a line.
• $+$: turn left by angle $\delta$ so the current state becomes $(x, y, \alpha + \delta)$
• $-$: turn right by angle $\delta$ so the current state becomes $(x, y, \alpha - \delta)$
• 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 $n \times n$ 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 $n^2$ 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 $\mathbb{A}$:
• Two contact points: the entry point $P_A$, and the exit point $Q_A$
• Two direction vectors: entry vector $\vec{p}_A$ and the exit vector $\vec{q}_A$
• Subfigure A is translated and rotated to align with its entry point $P_A$ and direction $\vec{p}_A$ 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.

## References

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