Plane-Filling Folding Curves on the Square Grid

Year: 2018 Authors: Jörg Arndt; Julia Handl

Core claim

All plane-filling self-avoiding folding curves on the square grid were determined up to order 53.

Topics

plane-filling curves, folding morphisms, L-systems, square grid, fractal tiles

Domains

fractal geometry, discrete geometry, combinatorics, numeration systems, generative art, algorithmic design, visualization

Methods

exhaustive search, L-system iteration, paper folding model, tile decomposition

Media

paper strip, square grid, computer rendering, fractal tiles

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2018 Conference Proceedings

Plane-Filling Folding Curves on the Square Grid

Jörg Arndt¹ and Julia Handl²

Technische Hochschule Nürnberg, Germany

${}^1$ Joerg.Arndt@th-nuernberg.de, ${}^2$ points.edges@gmail.com

Abstract

We determine all plane-filling curves on the square grid that are generated by folding morphisms, up to order 53. These morphisms are given in terms of Lindenmayer systems containing just two non-constant letters. This set of curves is the natural choice containing the Heighway-Harter dragon as its most simple element.

Introduction

The curve shown in Figure 1 is the best-known example from the class of curves we consider here. It is called the Heighway-Harter dragon (or just Heighway dragon) and was described in detail by Davis and Knuth in [3] and reprinted in [4]. See [6, Chapter 15, pp. 203ff] for a very accessible description of this curve.

Figure 1: The Heighway-Harter dragon.

The curve can be described using a Lindenmayer system (abbreviated as $L$ -system), a triple $(\Omega ,A,P)$ where $\Omega$ is an alphabet, $A$ a word over $\Omega$ (called the axiom), and $P$ a set of maps from letters in $\Omega$ to words over $\Omega$ , containing one map for each letter [1, Section 1.2] [7, Section 1.2, pp. 3ff]. The $L$ -system for the curve has the alphabet $\{L,R,+,-\}$ , axiom $L$ , and maps $L\mapsto L+R$ , $R\mapsto L-R$ , $+\mapsto +$ , and $-\mapsto -$ .

Here we describe L-systems equivalent to the folding morphisms given by Dekking [5]. These L-systems have two non-constant letters, L and R, and the production of L (the image W of the map $\mathrm{L}\mapsto \mathrm{W}$ ) specifies the L-system completely. The production of L is of the form $\mathrm{L}\mapsto \mathrm{L}?\mathrm{R}?\mathrm{L}?\mathrm{R}?\mathrm{L}?\mathrm{R}?\mathrm{L}\dots$ where each ? is either + or -. We omit the constant maps $+\mapsto +$ , and $-\mapsto -$ from here on. The production of R is obtained by reversing W, swapping letters L and R, and swapping letters + and -. For example, with $\mathrm{L}\mapsto \mathrm{L}+\mathrm{R}+\mathrm{L}-\mathrm{R}+\mathrm{L}$ we get $\mathrm{R}\mapsto \mathrm{R}-\mathrm{L}+\mathrm{R}-\mathrm{L}-\mathrm{R}$ .

Arndt and Handl

0: L 1: $\mathrm{L}+\mathrm{R}$ 2: $\mathrm{L}+\mathrm{R}+\mathrm{L}-\mathrm{R}$ 3: $\mathrm{L}+\mathrm{R}+\mathrm{L}-\mathrm{R}+\mathrm{L}+\mathrm{R}-\mathrm{L}-\mathrm{R}$ 4: $\mathrm{L}+\mathrm{R}+\mathrm{L}-\mathrm{R}+\mathrm{L}+\mathrm{R}-\mathrm{L}-\mathrm{R}+\mathrm{L}+\mathrm{R}+\mathrm{L}-\mathrm{R}-\mathrm{L}+\mathrm{R}-\mathrm{L}-\mathrm{R}$ 5: $\mathrm{L}+\mathrm{R}+\mathrm{L}-\mathrm{R}+\mathrm{L}+\mathrm{R}-\mathrm{L}-\mathrm{R}+\mathrm{R}+\mathrm{L}-\mathrm{R}-\mathrm{R}+\mathrm{R}-\mathrm{L}-\mathrm{R}+\mathrm{R}+\mathrm{L}-\mathrm{R}+\mathrm{R}-\mathrm{R}-\mathrm{R}-\mathrm{R}-\mathrm{L}+\mathrm{R}+\mathrm{L}-\mathrm{R}-\mathrm{L}+\mathrm{R}-\mathrm{L}-\mathrm{R}$

For rendering, draw a line of unit length for each letter L or R, make a turn by $+90^{\circ }$ for + and $-90^{\circ }$ for -. The initial position and heading are arbitrary. The curve shown in Figure 1 starts at the black part. The change of color mid-way indicates that the curve can be decomposed into two identical halves, connected by a $90^{\circ }$ turn.

Figure 2: The nth iterates for $n\in \{0,1,2,3,4,5\}$ of the $L$ -system for the Heighway-Harter dragon. Figure 3: A curve of order $R=5$ with maps $L\mapsto L+R+L-R+L$ and $R\mapsto R-L+R-L-R$ .

The order $R$ of a curve is defined as the number of letters in the production of the letter $L$ , for example, the curve shown in Figure 3 has order $R=5$ . We call the word obtained by $k$ -fold application of the maps on the axiom the $k$ -th iterate of the $L$ -system and the corresponding drawing the $k$ -th iterate of the curve. The first iterates of the $L$ -system are shown in Figure 2. We call a curve corresponding to a folding morphism a folding curve. The Heighway-Harter dragon is a folding curve. Another example of a folding curve is shown in Figure 3, the coloring shows that the curve consists of five copies of itself.

As the name suggests, all folding curves can be obtained by repeatedly folding a strip of paper. For a curve of order $R$ , divide the strip into $R$ pieces of equal length. Hold down the leftmost part of the strip while doing the following: For the $R-1$ creases to be made, read the sequence of turns in the production of the letter $L$ from right to left. If the turn is a -, then fold the rightmost part over the rest of the strip, otherwise fold it downward. Repeating this recipe $n$ times gives, after unfolding the strip such that the creases are at an angle of $90^{\circ }$ , a rendering of the $n$ th iterate of the curve. Figure 4 shows this for a curve of order $R=8$ and maps $L\mapsto L+R+L-R-L+R-L-R$ and $R\mapsto L+R+L-R+L+R-L-R$ .

Most L-systems lead to curves that are self-crossing and not plane-filling. Determining the L-systems

Plane-Filling Folding Curves on the Square Grid

Figure 4: Second iterate of a curve of order eight, via paper folding (left) and its computer rendering (right).

that do correspond to plane-filling self-avoiding folding curves is the main goal of this project. We have determined all curves up to order $R=53$ on the square grid.

Tiles, Carousels, and Numeration Systems

Each curve corresponds to a tile generated by the axiom $\mathrm{L}+\mathrm{R}+\mathrm{L}+\mathrm{R}$ as shown in Figure 5 for the curve with ID R13-13. The ID of each curve was assigned by the search program, the first number is the order, the second tells the position in the list of curves for this order. These tiles indeed tile the plane as illustrated at the right of Figure 6.

Figure 5: First iterate of the tile for the curve R13-13 with maps $L\mapsto L+R+L-R-L+R-L-R-L+R+L+R-L$ and $R\mapsto R+L-R-L-R+L+R+L-R+L+R-L-R$ .

Arndt and Handl

Figure 6: Third iterate of the tile for the curve R13-13 (left), decomposition of the tile into 13 scaled and rotated copies of itself (right).

Figure 7: The tile ${\Theta }_6$ for the curve R5-1 (left) and the fundamental region for the corresponding complex numeration system (right), where the digits $\{-1-i,-1,0,+1,+1+i\}$ are indicated at the centers of the five colored regions.

Plane-Filling Folding Curves on the Square Grid

Figure 8: Tile ${\Theta }_1$ for the curve R5-1, suggesting the values of the digits of the numeration system.

We use the symbol ${\Theta }_k$ for the $k$ -th iterate of the tile. For example, the third iterate ${\Theta }_3$ of the tile for the curve R13-13 is shown on the left of Figure 6. The tiles built from folding curves correspond to numeration systems, an integral complex basis together with a set of integral complex digits. The tile ${\Theta }_6$ of the curve with ID R5-1 is shown on the left in Figure 7. The numeration system has the basis $1+2i$ and digits $\{-1-i,-1,0,+1,+1+i\}$ . The choice of digits can be gleaned from the drawing of the first iterate of the tile shown in Figure 8. The fundamental region of the corresponding numeration system, the set of numbers of the form $0.\ast$ (that is, numbers with zero integral part) is shown on the right of Figure 7. The colors of the five parts on the right are chosen according to the digit after the decimal point.

The decomposition of the tile of the curve R13-13 shown at the right of Figure 6 was also obtained by drawing the fundamental region of the corresponding numeration system. Its basis is $-3+2i$ and the digits are $a+i$ with $-1\le a\le +2$ (top row), $a$ with $-2\le a\le +2$ (middle row), $a-i$ with $-2\le a\le +1$ (bottom row). The digits are suggested by Figure 5 rotated counter-clockwise by $45^{\circ }$ .

Figure 9: Drawings of 4 folding curves R13-13 starting at the origin.

Figure 9 shows the two carousels one can draw with the curve R13-13. The left image is obtained from the axiom $[\mathrm{L}]+[\mathrm{L}]+[\mathrm{L}]+[\mathrm{L}]$ , the right from $[\mathrm{R}]+[\mathrm{R}]+[\mathrm{R}]+[\mathrm{R}]$ , where the symbol [ pushes the current position and direction on a stack and ] retrieves both from the stack. Figure 10 shows both carousels are tiles for a lattice tiling of the plane.

Arndt and Handl

Figure 10: Tiling of the plane by curves R13-13.

The Search

The following conditions were used in our search. The two sufficient conditions were given by Michel Dekking. For a curve to be self-avoiding, it is sufficient if the tile ${\Theta }_1$ is self-avoiding [5, Theorem 1, p. 24]. For a curve to be plane-filling, it is sufficient that all edges inside the interior of ${\Theta }_1$ are traversed [5, Theorem 2, p. 27].

A necessary condition for a curve to be plane-filling is that $x^2+y^2=R$ where $R$ is the order of the curve and $x$ and $y$ are the components of the difference vector between start and end point of the curve.

A search for so-called simple curves, where the L-systems have only one non-constant letter, is discussed in [1]. Here we have no condition on the net rotation of a curve as for the simple curves where the net rotation has to be zero [1, Fact 4, Section 2.1.2]. Hence the possible orders $R$ (sums of two squares) are not limited to odd values as is the case for simple curves.

Figure 11: Two curves with the same shape (left and mid): the set of points traversed is the same (right).

The set of points of a curve is called its shape. We say that two curves have the same shape if they traverse the same set of points, possibly in a different order, and possibly after rotation and reflection of one of the curves. In general, more than one curve can have a given shape, as shown in Figure 11.

The freedom regarding the net rotation may explain that there is a significantly greater number of folding curves for a given order than simple curves. For all orders $R\le 53$ , we found 441272 shapes of folding curves, compared to 3653 shapes of simple curves reported in [1, Section 2.5, p. 14]. Figure 12 shows the number of curves for orders $\le 53$ , see also sequences A296147 and A296148 in [8]. We have no explanation for the

Plane-Filling Folding Curves on the Square Grid

Figure 12: Number $F(R)$ of folding curves and $S(R)$ simple curves of order $R$ .

apparent abundance of folding curves for even orders compared to odd orders, see sequences A296149 and A265685 in [8].

L L+R+L-R+L+R-L+R-L R R+L-R+L-R-L+R-L-R R9-1 #
L L+R+L-R-L-R+L-R+L R R-L+R-L+R+L+R-L-R R9-2 #
L L+R-L+R-L-R+L-R-L R R+L+R-L+R+L-R+L-R R9-3 # ## same = 1 R X
L L+R-L+R-L-R-L+R+L R R-L-R+L+R+L-R+L-R R9-4 # ## same = 2 Z T
L L+R-L-R-L+R+L+R-L R R+L-R-L-R+L+R+L-R R9-5 # # symm-dmrz

Figure 13: Descriptions of the curves of order 9.

The L-systems of all curves found up to order $R=40$ are given in the file short-folding-lsys.tar.xz at the URL http://jjj.de/3frac/. This archive unpacks into the directory short-lsys/f4/ containing one file for each order, such as lsys-r09.txt for $R=9$ . The contents of the file mentioned is shown in Figure 13. Each line contains the non-constant maps and the ID of the curve. A comment ‘same = N’ means that the curve has the same shape as the curve with ID R9-N. A comment ‘symm’ marks curves with shapes having 2-fold rotational symmetry.

Conclusion

We have determined all folding curves up to order $R=53$ , substantially increasing the number of known curves of this type. With this massive collection of folding curves available, it is our hope that artists, engineers, and scientists will look for what can be done with them. One such use is to look for constructions of families of curves with extremal properties. For example, the curve of order 50 on the left in Figure 14 led us to believe that it may be part of a family for which an explicit construction exists: an algorithm that for each $n\ge 1$ returns an L-system for one curve of order $R(n)$ . Indeed, there is a construction for such curves of orders $R(n)=n^2+1$ for all $n\ge 1$ . The curve of order $R=19^2+1=362$ is shown on the right in Figure 14. The Hausdorff dimension of the tile gets arbitrarily close to 2 for large $n$ , as does the dimension of the border of the curve. In addition, the net turn of the curve is linear in $n$ , hence increasing without bounds. We found quite a few such constructions, which will be presented in a future publication.

Arndt and Handl

Figure 14: The tiles ${\Theta }_1$ of a curve of order 50 (left) and 362 (right).

Acknowledgments

It is our pleasure to thank Michel Dekking, Marvin Dittrich, and Edith Parzefall for their help in preparing this manuscript. We would also like to thank the three anonymous reviewers, whose detailed suggestions led to a significantly improved presentation.

References

[1] J. Arndt. “Plane-filling Curves on all Uniform Grids.” arXiv:1607.02433 [math.CO], 2016. https://arxiv.org/abs/1607.02433. [2] J. Arndt and J. Handl. “Plane-filling Curves on Transitive Grids.” Bridges Conference Proceedings, Jyväskylä, Finland, Aug. 9–13, 2016, pp. 537–540. http://archive.bridgesmathart.org/2016/bridges2016-537.. [3] C. Davis and D. E. Knuth. “Number Representations and Dragon Curves, I and II.” Journal for Recreational Mathematics, vol. 3, 1970, pp. 61–81 and pp. 133–149. [4] C. Davis and D. E. Knuth. “Number Representations and Dragon Curves.” Selected Papers on Fun and Games, CSLI Publications, 2011, pp. 571–614. [5] M. Dekking. “Paperfolding Morphisms, Planefilling Curves, and Fractal Tiles.” Theoretical Computer Science, vol. 414, no. 1, 2012, pp. 20-37. https://arxiv.org/abs/1011.5788 (preprint). [6] M. Gardner. Mathematical Magic Show. The Mathematical Association of America, 1978. [7] P. Prusinkiewicz and A. Lindenmayer. The Algorithmic Beauty of Plants. Springer-Verlag, 1990. http://algorithmicbotany.org/papers/#abop. [8] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences. 1964-2018. http://oeis.org/.