The Family Tree of Fractal Curves A taxonomy of plane-filling curves using complex integer lattices Jeffrey Ventrella 
www.fractalcurves.com ISBN 978-0-9830546-3-4 Copyright © 2019 by Jeffrey Ventrella 
www.eyebrainbooks.com 
Tsunami curve Contents Acknowledgments 1 Introduction 2 Taxonomy 3 Iteration 4 Morphology 5 Family Resemblances 6 Undiscovered Curiosities References 
Acknowledgments I would like to thank Vince Matsko for his in-depth review, advice, and editing from the perspective of a math educator. I would also like to thank Linda Jay for her copyediting work. Thanks to brother Philip, Scott Bowling, and Wayne Bollinger for early creative explorations. Much thanks to Dr. David Burton for ideas at the intersection of math and art. Thank you Kirk Israel for advice and suggestions. Thank you Julia Smith for creative sessions in exploring the taxonomies of fractal curves. Much gratitude goes out to the following people: Scott Kim, Gary Walker, Beth O’Sullivan, Gary Teachout, Henry Segerman, David Olsen, Christoph Bandt, Jörg Arndt, Benjamin Trube, Craig Kaplan, Eddie Elliot, David Mitchell, and Ed Zajec. I would like to thank Adam Goucher for pointing me to the rich universe of complex integer lattices, and for reviewing a draft of the book. And finally, thanks to Nuala Creed, for her continual support and love. 
A personal note on the math in this book This book is intended for college-educated readers who share a fascination with geometry, fractals, and number theory. My schooling did not include math other than the bare minimum requirements. My journey began in the practice of visual art. I happened upon fractals and computer programming as part of an exploration in visual expression through algorithms. When I first laid my eyes on Mandelbrot’s book, The Fractal Geometry of Nature, I was struck by the illustrations of strange, novel forms. Over the years, I would periodically return to the book for a fresh look. Each time, I would engage in a bit more of the text, which expanded my vocabulary…and my collection of books. The math gradually began to take shape. The illustrations in Mandelbrot’s book served as my initial impetus to learn more. As a visual thinker, this was my catalyst for attaining knowledge. This journey has resulted in many thousands of hand-drawn diagrams and a lot of software, developed over the span of more than three decades. It became a lifelong obsession. I have always wanted to write a book that triggers the same curiosity and wonder that I had experienced…for readers who are not necessarily trained in math—because I knew from personal experience that any curious mind could be stimulated to experience math—through pictures and words. This book uses very little math notation, and there are no proofs. There are several conjectures. In some parts of the book I venture out a bit beyond my normal comfort zone—a risk I consider worth taking. I would encourage any reader to work out proofs and generalizations—to take over where I have left off. 
1. Introduction Imagine that you are a paleontologist. You set sail to a remote island to find fossils. When you arrive at the shore, you quickly begin searching. Then you happen upon a rocky plain with strange-looking fossils. Preserved in the rocks are numerous organic shapes, indicating that several remarkable species once flourished on this island. Although the shapes have magnificent variation, there are also some common themes, body shapes, and patterns. The fossils are well-preserved, and you can even detect complicated vascular patterns within their bodies. 
Figure 1.1. Two curves with the same overall shape Upon returning to your lab on the mainland, you begin studying the hundreds of photographs you took while you were on the island. You can see that many creatures had similar dragon-like bodies, with the same horn-like protrusions, but they were clearly different in their internal details. What accounts for these similarities…and for the differences? Puzzles abound. In one specific site on the island, you found a large collection of fossils in a cluster. Strangely, their body shapes are very different from each other—having two distinct profiles. 
Figure 1.2. Two related curves (splined) One fossil has a craggy boundary, while the other has a straight boundary. Could it be that they are actually related, but exhibit a different expression of the same common genetic base? Classification Like a morphologist attempting to make sense of the varied macrostructures in organisms, we will embark on a similar exploration…with fractal curves. It is as if these curves were natural organisms, uncovered after millions of years in hiding. They are calling out for our analytical eye to classify and organize them into a hierarchy: a family tree. This book sets out to do just that. But unlike Carl Linnaeus in the 1700s, who laid down the foundations of modern taxonomy, we have the benefit of knowing the entire “genetic code” that is responsible for this vast array of forms. In a way, we humans are both the creators and the discoverers of these forms. 
Figure 1.3. A plane-filling curve (splined) So, you may ask: if we are already able to generate these curves with computer algorithms, shouldn’t we therefore know everything there is to know about them? The answer is no, not entirely: fractal geometry is not an exercise in making explicit mathematical concepts visible; fractals embody chaos. They can be very unpredictable—even when the process of generation is completely deterministic…like the fractal curves in this book. 
Figure 1.4. Mandelbrot’s Quartet When fractals and chaos theory invaded the clean-edged world of geometry, new perspectives on nature blossomed. With a menagerie of strange beasts that are so complex, so organic, so detailed, we cannot know everything there is to know about them. The archetype of this is the Mandelbrot set [22]: a fractal object first discovered in 1978 that continues to awe and inspire, and will continue to do so as long as we have the computational tools to zoom ever deeper into its remote crevices. If you happen upon fractal geometry from the viewpoint of visual language and design, you may be inclined to take the perspective of an explorer—applying visual intuition and pattern-finding—and work your way towards a mathematical understanding. That was the impetus for the ideas that eventually came together to form this book. And after more than three decades of exploration and design, a taxonomy has been formulated that places the classic plane-filling curves described in Mandelbrot’s The Fractal Geometry of Nature [22] (and many more discovered since) under one system. But a taxonomy is not very useful unless there is an underlying logic for the diversity of shapes being studied; otherwise, it is an arbitrary exercise based on surface appearances. In the case of fractal curves, a question comes to mind: is there a fundamental “nature” behind these forms? In the process of searching for fractal curves that are space-filling and non-overlapping, a consistent logic starts to take shape—calling out for more exploration. This book describes a taxonomy that includes a large class of plane-filling curves—including the classics. It makes connections between the morphologies of plane-filling curves and concepts from number theory. 
Figure 1.5. A curve of the E(3,0) family (splined, on a triangular initiator) A Brief Introduction to Plane-filling Curves Let’s begin with a cursory overview of some basic concepts and approaches to generating fractal curves. This will help to establish some context for describing the taxonomy in the next chapter. If you magnify a line segment, it still looks straight. If you magnify any portion of a circle, it looks less like a circle and more like a straight line. With a sufficiently deep magnification of any portion of the circle, it appears identical to a straight line. This is a property that lines and circles have in common. Fractal curves do not have this property: they never appear straight—no matter how deep the magnification; fractal curves bend and curl…at every level of magnification. 
Figure 1.6. The Koch curve magnified to illustrate the concept of infinite detail The Koch curve (Figure 1.6 ) is not a plane-filling curve, but it serves as a good example for introducing fractal curves in general. It will appear a few times throughout the book. The figure shows how the Koch curve is constructed, starting with the generator (a shape made of four segments with a triangle-shaped bump in the middle). The first step consists of replacing each of the generator’s four segments with a scaled-down copy of the generator. This is called “edge-replacement” (it can also be called, “Koch construction” or “self-substitution”). In the case of the Koch curve, this replacement causes four new smaller bumps to appear on the generator. This process is repeated over and over again. Eventually, the newly-accumulated bumps become so small that we can no longer see them. But the process goes even further: in a true fractal curve, the process is carried on to infinity. Thus, every bump, no matter how small, has infinitely many smaller bumps on it. Every time a new bump is added, the curve grows slightly longer…in fact, in a fractal curve, it becomes infinitely long at the limit. This may seem counterintuitive at first, considering that the entire curve—from end to end—occupies a finite space. But the process of iteration is done infinitely many times. This is the key to how fractal curves are able to push their way into a higher dimension. Fractal Dimension Figure 1.7 shows three topological types of fractals inserted between the integer dimensions. Every fractal curve has a fractal dimension (Hausdorff dimension) between 1 and 2. A straight line has a fractal dimension of 1. The Koch curve has a fractal dimension of 1.26186. The higher the dimension, the more “space” the curve fills. If a fractal curve doesn’t overlap with itself, and if it is so curvy that it essentially visits every point in a planar area, then it is a plane-filling curve. It defines a continuous mapping from a lower-dimensional space (a line) into a higher-dimensional space (a plane). Its fractal dimension is 2. 
Figure 1.7. Fractals have non-integer dimensions, with fractal curves ranging from 1 to 2 Plane-filling curves that are “self-avoiding” (never touching themselves, and having no contact points) have special properties. As an example of a self-avoiding curve, figure 1.8 shows the process of generating a curve that was discovered in the process of developing this taxonomy. It never touches itself, no matter how densely it fills the shape—even though the final state looks completely filled-in to the eye. But if you were able to magnify it enough, you would see that the lines are still not touching. 
Figure 1.8. The first few iterations of the growth of a self-avoiding curve The angles between the four connected segments in the Koch generator are 60, -120, and 60. Imagine that the Koch curve were made of hinged segments, and you could “squeeze” it so that all the angles change, becoming more acute, which would cause the distance between its endpoints to decrease from 3 down to 2 (Figure 1.9). When the distance reaches 2 it cannot be squeezed any further—there are no gaps left. This squeeze would cause the angles of the generator to become 90, -180, and 90. This curve would not be self-avoiding: it would be maximally-touching. 
Figure 1.9. The Koch curve gets squeezed to become the Cesàro Sweep Figure 1.10 shows a curve derived from the Koch curve created by Wolter Schraa [30]. It shows a continual squeezing of the angles in the Koch curve, causing its fractal dimension to change from 1 to 2 along the extent of the curve. The profile of the Koch curve appears about mid-way in the curve. The right side shows the profile of the Cesàro Sweep, which has a fractal dimension of 2. 
Figure 1.10. A variation of the Koch curve showing the concept of fractal dimension For explanations of fractal dimension, see Tricot [34], and Kayne [21]. Doodling 
Figure 1.11. Self-avoiding doodles drawn in the sand A doodling line can be simulated on a computer, using any number of iterative methods—reminiscent of animal foraging paths and other natural processes. A randomly-generated curve has no predictable structure or symmetry—it cannot be described in an elegant or terse way. In this book, the focus is instead on describable emergent structures that arise deterministically from relatively simple initial descriptions, and relatively simple rules of growth. There is no randomness, but there is plenty of chaos and complexity. Infinity vs. Visual Threshold Anyone can draw a doodle that doesn’t overlap or cross itself. But to qualify as a true plane-filling fractal curve, it would have to be infinitely long, drawn with an infinitely-thin pencil, and have infinitely small twists and turns. Even more strange: in order to be completed in finite time, it would have to be drawn at infinite speed. Although a fractal curve has infinite length and infinite detail at all scales, the special properties of fractals at the limit is not central to the taxonomy described in this book. The details that emerge through iterating a generator reach a visual threshold when the line segments are so small that they are invisible to the eye—the overall shape is all that can be seen. We are less concerned with what lies beyond a certain threshold—particularly when the nature of that detail remains the same on all levels beyond the macro-scale—due to the curve being self-similar. Kinds of Fractal Curves Fractal curves come in many forms, and they arise—sometimes unexpectedly—as a result of many kinds of iterative processes. For comparison, figure 1.12 illustrates a few fractal curves generated using three different methods: (a) approximating the boundaries of sets in the complex plane determined by iterated functions, such as the Mandelbrot set; (b) plotting certain recursive functions along the real number line, such as the Weiertrass function; and (c) constructing curves based on recursive geometrical replacement, such as the Minkowski sausage. 
Figure 1.12. Three kinds of fractal curves Edge-replacement is a special kind of recursive geometrical replacement that is specific to line segments (a more general technique being iterated function systems [18]). Edge-replacement is based on replacing the segments in a fractal generator with smaller copies of the generator. This is illustrated in Figure 1.13, which shows construction of the Koch curve and the Dragon of Eve [35]. 
Figure 1.13. Construction of the Koch curve and the Dragon of Eve Edge-replacement allows copies of the generator to be flipped (rotated by 180 degrees), as demonstrated with the construction of the Dragon of Eve, at the right of Figure 1.13. In some curves, copies of the generator can also be reflected about a segment—this will be explained later. Fractal curves that are constructed in this way are self-similar: they exhibit the same features at multiple scales, rotations, and locations. Teragons As a curve is generated, it undergoes a progressive increase in detail at each iterative step. The resulting shape is called a “teragon” [22]. In this book, the results at intermediate steps are referred to as “teragon orders.” For example, Figure 1.8 shows teragon orders 1-6 (or “teragons 1-6”) of a particular curve. “Teragon 0” is simply a line segment. Edge-Replacement vs Node-Replacement Edge-replacement is distinct from another technique called “node-replacement” [26]. A popular curve that uses node-replacement is the Hilbert curve [17] (Figure 1.14). (In a later chapter, node-replacement curves will be revisited in terms of their relationship to edge-replacement curves). 
Figure 1.14. Construction of the Hilbert curve The top-left of Figure 1.14 shows four squares, ordered in a clockwise manner; the centers of these squares are the nodes. To the right of that is the generator, which consists of three lines that connect nodes 1 to 2, 2 to 3, and 3 to 4. Each node is replaced with a scaled-down and rotated copy of the generator. Note that the Hilbert curve (as well as all node-replacement curves) are not strictly self-similar, because at every iteration, a few extra connective segments are required to close the curve (upper-right of Figure 1.14). These segments alter the component shapes that make up the resulting curve at every level. L-Systems There are as many algorithms to construct fractal curves as there are creative people in the world who can write code. But most of the algorithms fall into a few common types. One of the most common is L-systems [26], using turtle geometry [1] for drawing lines. Although L-systems are not used to generate the fractal curves in this book, they are important and widely-used, and so the technique will be briefly mentioned here. In an L-system, a fractal generator is specified as an axiom (a string of symbols). Each symbol can be replaced with other strings, using a set of rules for recursive string rewriting. L-systems encode an entire geometrical transformation process into a one-dimensional string of instructions. Those instructions are fed to a turtle (an entity that can rotate in place and move forward, optionally drawing lines as it moves). Figure 1.15 shows how an L-system can be used to construct the Koch curve. Each F is replaced by the string specified in the rule, causing the string to grow to an arbitrary length. 
Figure 1.15. An L-system for constructing the Koch curve L-systems are abstract: they are separate from the manner in which the abstract symbols are interpreted into drawing instructions. In contrast, the plane-filling curves described in this book are wedded to a particular space: a lattice of points with algebraic properties. That space has inherent structure within. While it is not as general as an L-system, its inherent structure provides a rich and fertile backdrop for discovering and exploring many properties of plane-filling curves. More abstract is not necessarily better. Research The book, Space-Filling Curves, by Hans Sagan [29], provides an overview of the classic curves introduced by Hilbert, Sierpinski, Peano, and others, with an emphasis on topology and mathematical analysis. Another book with the same title by Michael Bader [3] explores space-filling curves with emphasis on applications in scientific computing and data processing. These authors are less concerned with the overall shapes of fractal curves, and typically refer to the square as the space of interest, describing how a single line can map to that space, as exemplified by the Hilbert curve. Others have explored various geometrical macro-structures that emerge from iterating over several varieties of fractal generators. Dekking [10] analyzed plane-filling curves in terms of iterated paper-folding. Imagine having a thin strip of paper that you can fold any number of times. Each fold increases the number of creases exponentially, as shown in Figure 1.16. The creases are labeled D for down and U for up. A simple repetitive folding process creates a sequence of turns that—when unfolded to form 90 degree angles—make up a self-similar structure: the Harter-Heighway Dragon curve [9] (abbreviated from now on as “HH Dragon”). 
Figure 1.16. Paper-folding to create the HH Dragon curve The structures that emerge from iterative processes have been studied by many fractal curve explorers, such as McKenna [23], Irving [19], Ryde [28], Karzes [20], Fathauer [11], Fukuda [13], Ventrella, [35], and many others, a few of whom will be mentioned later in the book. The list of fractal curve explorers is growing; it would not be possible to credit all of them in this book. The Lattice Curves with low fractal dimension (close to 1) are almost straight. They have plenty of room to wander around with little risk of bumping into their own paths. Higher-dimensioned curves are more susceptible to self-collision. At dimensions close to 2, it becomes necessary to use a lattice (or a grid) as a guide to avoid a complete mess (the reason for this will become more apparent in the next chapter). When searching for new plane-filling fractal curves, confining the search to a lattice is therefore very useful, as demonstrated by McKenna [23] and also by Arndt [2], who reveals novel curves in various grids, using L-systems. Complex integers (introduced in the next chapter) provide a lattice framework, and they also happen to be rich in terms of number theory. Several techniques for generating a variety of fractal structures using complex integers have been studied by Gilbert [14], and Stange [31]. Complex integers can also be used as a framework for studying (and generating) plane-filling fractal curves. This brings us to a core theme in the book: a lattice-based framework for categorizing edge-replacement plane-filling fractal curves, and its relationship to complex integers. Much of the inspiration for placing fractal curves in a complex integer framework is based on suggestions by Adam Goucher [15]. 
Figure 1.17. A self-crossing curve of the E(3,0) family (splined) |