Puzzling Plane-Filling Curves
Year: 2019 Authors: Jörg Arndt; Julia Handl
Core claim
Curve-sets with different motifs can still satisfy a tile-condition, producing self-avoiding plane-filling curves and new self-similar puzzles.
Topics
plane-filling curves, self-similarity, puzzle construction, curve-sets
Domains
fractal geometry, tiling theory, Lindenmayer systems, combinatorics, mathematical puzzles, generative design, visual patterning, paper-based construction
Methods
motif substitution, tile-condition testing, iterative refinement, grid-based tiling
Media
square grid, triangular grid, colored line diagrams, puzzle pieces
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.
Page 1
Bridges 2019 Conference Proceedings
Puzzling Plane-Filling Curves
Jörg Arndt¹ and Julia Handl²
Technische Hochschule Nürnberg, Germany
¹Joerg.Arndt@th-nuernberg.de, ²points.edges@gmail.com
Abstract
From a generalization of a construction for plane-filling curves we create puzzles where each curve from a set is decomposed into a subset of smaller copies of the curves. These puzzles are very challenging and the constellations obtained are beautiful examples of non-trivial self-similarity.
Introduction
Let’s start with a certain class of plane-filling curves we call simple curves. They correspond to Lindenmayer systems with just one non-constant letter, as described in [1].
These curves can be obtained by choosing a motif, a sequence of edges with turns by 90 degrees between them. One such motif is shown on the left of Figure 1, the turns are shown slightly rounded to make the path visible. Replacing each edge of the motif with the motif itself gives a longer curve, shown in the middle of the same figure. The colors are inherited from the motif.
Figure 1: Motif (left), second iterate (middle), and fourth iterate (right) of a curve.
A motif is the first iterate of a curve, the higher iterates are obtained by repeating the replacement process. Every such curve is self-similar by construction, it can be decomposed into smaller rotated copies of itself, as can be seen in the fourth iterate on the right of Figure 1.
Since the number of edges in the motif of the curve is 13, the curve consists of 13 smaller versions of itself, suggesting a puzzle. We use the border of the second iterate of the curve for the pieces of the puzzle, see Figure 2. To obtain the border of a curve on the square grid, draw a square around each edge such that the edge is the diagonal of the square and take the edges of these squares that are the boundary of this arrangement. The solution of the puzzle corresponds to the third iterate of the curve. The pieces occur in the four possible orientations as indicated by the colors.
Page 2
Arndt and Handl
Figure 2: The second iterate of the curve becomes a puzzle piece (left), 13 such puzzle pieces assembled into the shape of the third iterate (right).
A new class of plane-filling curves
Not every motif leads to a self-avoiding and plane-filling curve. Whether a given motif ‘works’ can be determined by using tiles. While the grid consists of only one shape (squares), the configurations we need to consider are the squares together with their drawing directions. This gives us two kinds of tiles, shown in the top row of Figure 3. We use the symbols 1 (right), 2 (up), 3 (left), and 4 (down) to describe the edges of the tiles. The motifs are shown respectively in black (1), blue (2), red (3), and green (4). If the interiors of both tiles (in the first iterate) are completely filled with edges and no crossing occurs, the curve is self-avoiding and plane-filling. We call this criterion the tile-condition. For example, the motif we chose works, because both tiles fulfill the tile-condition, as illustrated in the bottom row of Figure 3. The lightly colored lines are the vectors between start and endpoint of the motifs, for instance for the first motif (drawn in black). Dekking [2] proved the tile-condition for a slightly different class of curves generated by folding morphisms.
Figure 3: The two square configurations that need to be considered (top) and the two tiles obtained by drawing four identical motifs in counter-clockwise and clockwise orientation (bottom).
Our crucial observation is that the tile-condition is still valid when using different motifs for the four directions in the tiles. We now have a curve-set using four possibly different motifs. This concept generalizes both the simple curves considered in [1] (all four curves of the tiles are identical) and the folding curves considered in [2] and [3] (one curve and its flip are used to form the tiles).
Page 3
Puzzling plane-filling curves
Figure 4: Tiles of the curve-set with three different motifs. In the left image, the edges around the gray striped area in the left tile that were part of the black motif have been moved to the green motif (solid gray area). In the right image, the edges have been re-attached from the black to the green motif as well.
A convenient way to create a curve-set is to take one of the tiles of a simple curve and make small changes to the motifs. The tile on the right of Figure 4 is the same as the one in Figure 3, except for the gray filled square. First, the square was part of the first motif, now it is part of the fourth. This leaves us with one shortened motif (1), two motifs that are still identical up to rotation (2 and 3) and one lengthened motif (4). However, not only three but four shapes occur in higher iterates, as shown in Figure 5.
The edge-substitutions for the curve we started with are , , , and . For the curve-set the maps for 1 and 4 are changed into and .
Figure 5: Puzzle pieces using the second iterate of the curve-set.
The self-similarity of the simple puzzle, the decomposition into smaller copies of itself, gets more complicated for sets of curves. Each curve in the set can be decomposed into smaller copies of itself and the other curves of the set, as shown in Figure 6. This means we have four new puzzle challenges instead of one, and much more difficult ones! For solving the puzzle it may help to notice that all pieces of the same shape have the same orientation (and color), see Figure 6.
The four motifs in the third iterate can also be assembled into the forms of the two tiles for even more puzzling fun, as illustrated in Figure 7. Alternatively, 13 tiles put together do form a bigger tile, as shown in Figure 8. This illustrates that the tiles do indeed tile the plane by translation without rotation.
Page 4
Arndt and Handl
Figure 6: Self-similarity for the curve-set: each curve can be decomposed into a collection of copies of itself and the other curves in the set.
Figure 7: The two tiles of the curve-set, colored to highlight each of the curves in the previous figure.
Figure 8: The two tiles of the third iterate decomposed into smaller tiles.
Page 5
Puzzling plane-filling curves
How to create your own curve set, it’s easy!
The situation on the triangular grid is quite similar to what we have seen. There are edges pointing in three directions and two tiles with different orientations, as shown in Figure 9. For our example on the square grid we used the tiles of a simple curve and modified them into a curve-set. Turns out there is a simple way to create a curve-set from scratch.
Figure 9: The three types of edges denoted by 1 (blue), 2 (red), and 3 (green) forming the configurations of the tiles (top) and first iterates of the tiles for a curve-set (bottom).
Figure 10: Construction of a curve-set, see text.
We actually found the curve-set shown in the bottom row of Figure 9 as follows. Firstly, combine the two configurations for the tile into what resembles an infinity symbol as shown on the left of Figure 10. After fixing the direction on any edge of the grid, the directions on all edges are fixed. Now chose an arbitrary vector on the triangular grid and put five of them on the grid according to the infinity symbol. One example is shown using lightly colored vectors in the middle of Figure 10. Each vector marks the start and endpoint of the motifs we will create. Draw edges for the curves such that the interior is completely filled in and crossings are avoided. Keep in mind that motif 1 and 2 appear twice, motif 3 only once, any change must be copied to the identical curve. The allowed turns are by 0 (no turn) or degrees. There are many possible ways to complete the curve-set. One is shown on the right of Figure 10. Compare the upper and lower half with the
Page 6
Arndt and Handl
tiles in Figure 9. The edge-substitutions in our example are , , and as indicated by the numbers on the right of Figure 10.
Figure 11: Fifth iterates of the tiles for the curve-set.
The borders of the tiles happen to be identical (rotate the right one clockwise by 60 degrees). This is true even for higher iterates, as shown in Figure 11. This is not the case in general.
With those three different motifs, we get three new puzzle challenges, shown in Figure 12. Note that this time we only use a subset of the set of curves to get the decomposition of the first curve.
Figure 12: Decompositions of the curves into smaller copies of themselves.
More puzzle pieces, please!
It is possible to use even more motifs than there are directed edges. One way of using eight edges is indicated in Figure 13, this leads to a total of four tiles that need to be considered. The first and fifth iterates the tiles are shown in Figure 14. The choice of eight motifs in the top row of Figure 14 corresponds to the curves in Figure 15.
The tiling of the plane by this curve-set is shown in Figure 16. It appears that curve-sets with an arbitrary number of curves exist, this is the subject of ongoing work.
Page 7
Puzzling plane-filling curves
Figure 13: The grid graph for the square grid with eight distinguished edges. The mutual configurations of the edge-types determine the tiles.
Figure 14: The four tiles of a curve-set of eight curves: 1234, 5678, 1836 and 5472. First iterates on top row, fifth iterates on bottom row.
Figure 15: The eight curves of the curve-set, decomposed into smaller copies of some of the curves.
Page 8
Arndt and Handl
Figure 16: The curve-set tiling the plane.
The edge-substitutions for the eight curves are , , , , , , , and .
Conclusion
We use a generalization of two known families of plane-filling curves to establish the concept of a curve-set, where the motifs of a tile do not need to be identical. The self-similarity of these curve-sets leads to new challenging and exciting puzzles. With our instructions, building such a puzzle-set is fun and easy, try it yourself!
Acknowledgments
We are grateful to Edith Parzefall, Marvin Dittrich, and Joachim Kopp for their help in preparing this manuscript. The presented material is in part a spin-off of a project supported by KONWIHR, the Bavarian Competence Network for Technical and Scientific High Performance Computing.
References
[1] J. Arndt. “Plane-filling Curves on all Uniform Grids.” arXiv:1607.02433 [math.CO], (2016). https://arxiv.org/abs/1607.02433. [2] 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). [3] J. Arndt, J. Handl. “Plane-filling Folding Curves on the Square Grid”, Bridges Conference Proceedings, Stockholm, Sweden, (2018), pp. 179-186. http://archive.bridgesmathart.org/2018/bridges2018-179..