The Art of Space-Filling Domino Curves

Year: 2024 Authors: Douglas M. McKenna

Core claim

Automated enumeration reveals rare domino coverings and motifs that generalize Peano curves into aesthetically rich, self-similar designs.

Topics

space-filling curves, domino coverings, self-similar tilings, recursive motifs, visual design

Domains

combinatorics, tiling theory, fractal geometry, enumeration, mathematical art, abstract geometric design, pattern generation, Islamic-inspired motifs

Methods

computer enumeration, recursive construction, manual motif search, self-similar replication

Media

domino tilings, recursive line drawings, filled approximation paths, framed figures

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 2024 Conference Proceedings

The Art of Space-Filling Domino Curves

Douglas M. McKenna

Mathemæsthetics, Inc., Boulder, Colorado, USA; doug@mathemaesthetics.com

Abstract

Certain self-similar domino coverings support space-filling curve constructions akin to how the original Peano curve construction and its generalizations fill squares. But for domino coverings and motifs, there are interesting constraints and freedoms with which to play. Upon enumeration of coverings and relatively rare motifs, approximation paths for space-filling, space-underfilling, and space-overfilling curves support visually intriguing, self-negative tilings, some with lovely fractal interiors or whose finite self-crossing filigree patterns are reminiscent of Islamic designs.

Introduction

Peano’s first space-filling curve construction [4], when visualized as a strictly recursive edge-replacement motif, comprises nine piecewise-connected line segments. Each is the diagonal of an oriented sub-square in a $3\times 3$ , or order-3, subdivision of a square. Upon infinite recursive edge-substitution—replication with a contractive linear transformation, possibly including mirroring—the limit set is a continuous curve from lower left to upper right, reaching every point in the original square region. But as Figure 1 shows, a drawing of each increasingly detailed approximation path is nothing more than a regular crosshatching of its bounding square. When the approximation path is filled on one side, a checkerboard pattern arises, due to regular self-contact of lines at every other sub-square corner. When the square is rotated upside down, white and black swap, i.e., it is a self-negative pattern (see [2] concerning self-negative order- $n$ Peano motifs).

Figure 1: The Peano Curve edge-replacement motif, applied recursively, with path filled on one side.

Generalizing the Peano Construction to Dominos

When a square subdivided into nine equal sub-squares is stretched horizontally by a factor of two, each sub-square turns into a $1\times 2$ rectangle, or domino, nine of them covering a $3\times 6$ rectangle. The larger rectangle and each domino have the same shape, thereby forming a self-similar “rep-tiling” [1] of the larger rectangle. Any now-stretched Peano motif remains piecewise-connected, still nine line segments long, still crosshatching from the lower left to upper right. Each stage in the recursive construction—as well as the limiting space-filling curve—maintains its salient properties under this simple linear transformation.

But dominos have less symmetry than squares, and can be oriented in two ways. Using them to tile a larger rectangle thus becomes much more combinatorially rich. The Kasteleyn-Fisher-Temperley formula counts the number of ways $M(n,m)$ that an $n\times m$ rectangle can be tiled, or “covered,” by dominos [6]. Here, self-similarity requires $m=2n$ , so we’ll use the term order- $n$ to denote an $n\times 2n$ domino covering. An

McKenna

order- $n$ domino curve motif is then an open-ended path of $n^2$ piecewise-connected, diagonal line segments from lower left to upper right; motifs can be replicated either congruently or in mirror image form.

Other than for program verification, counting coverings isn’t as helpful as an automated enumeration that constructs all possible coverings, at least for small $n$ . Figure 2 verifies that $M(2,4)=5$ and $M(3,6)=41$ .

Figure 2: All order-2 and order-3 self-similar domino coverings. Only one supports a diagonal-based motif.

Using Figure 2, it is possible to ascertain manually that, other than the highlighted covering, none supports a motif. The highlighted covering is just the stretched Peano motif, shown in Figure 1. The question arises: Is this dirth of solutions true of all higher order- $n$ coverings? Unfortunately, when $n=4$ the combinatorial explosion begins with 2245 order-4 coverings of the $4\times 8$ rectangle. For $n=(5,6,7)$ the counts rise dramatically to (185921, 106912793, 90124167441), precluding any manual determination of the answers. Most coverings support no motifs at all. A few coverings support multiple solutions; others just one. A motif path with no lines self-contacting at any domino corner is called locally self-avoiding.

Even rarer among both coverings and their motifs are those that we call rotatable: they remain unchanged when rotated by $180^{\circ }$ . Computer enumeration of the 2245 order-4 coverings finds that 65 are rotatable. None admits a motif, whereas eight non-rotatable order-4 coverings do (see Figure 3, top). For order-5 coverings, I found that 287 of the 185,921 are rotatable. Only four admit a motif, as highlighted in the lower half of Figure 3, which also shows the additional 16 non-rotatable coverings that admit a motif. The first of the four is the usual crosshatch, i.e., Figure 1’s stretched Peano covering generalized for order-5 (odd orders, per [4]).

Figure 3: Eight order-4 and twenty order-5 coverings that support at least one motif. The four highlighted motifs are rotatable. The framed motif is also locally self-avoiding.

When coloring area on one logical side of a piecewise-connected, space-filling approximation path, rotatability supports creating self-negative designs. Figure 4 is based on the second recursive stage for the red-framed motif in Figure 3; Figure 5 relies on its highlighted neighbor motif. Due to motif mirroring between consecutive, adjacent dominos that share a long edge, the recursive productions are not self-avoiding paths. Large portions nonetheless exhibit self-avoidance, allowing one’s eye to integrate connected areas of color into related and repeated forms, like jigsaw puzzle pieces. There is also an intriguing tension between the rectangular area being filled vs. the ubiquitous diagonality of all the path segments, many of which align

The Art of Space-Filling Domino Curves

Figure 4: “Domino Mural I” 2023. 2nd recursive approximation (filled on one side) of order-5 self-negative domino-filling curve.

co-linearly even when they are not consecutive in the path. By construction, there is repetitive self-reference, although the hierarchical self-reference is hidden because it is overwhelmed by the space-filling homogeneity. The second recursive level best balances structure against texture; I find myself constantly mystified looking at Figure 5 as it intimates reference, mirroring, rotation, and deliberate, quasi-homogenous, elegant form.

Figure 5: “Domino Mural II” 2023. 2nd recursive approximation (filled on one side) of second order-5 self-negative domino-filling curve.

Over-Filling Motifs with U-Turns

Space-filling curves are, in the limit, mappings from the unit line segment onto all points in a higher-dimensional region. But these mappings cannot be bijective (one-to-one). They are always surjective: the curve must reach infinitely many points within the region (here an $n\times 2n$ domino) more than once, regardless of

McKenna

whether approximation paths that show sub-tile sequences are self-contacting or not. And finite approximation paths can self-contact not only at sub-tile corners, but also (in general) along entire path line segments (see, e.g., the discussion of self-contacting tile paths for Hilbert Curve generalizations in [3]).

Of the 41 order-3 coverings in Figure 2, ignoring the first Peano generalization, two coverings are still rotatable. One the mirror image of the other, each of them shows an interesting way to extend the idea of motif by using over-filling, whereby certain dominos are filled twice. At the same time all recursive approximation paths remain piecewise connected, which in turn guarantees the limiting curve will be continuous, even if over-filling. One way relies on U-turns; the other relies on crossovers.

The U-turn variation is illustrated in Figure 6. The first four diagonal line segments of the motif travel from the lower left corner up-right, down-right, right-up, and then right-down. This leaves the path dead-ended in the lower right corner (circled in red), with nowhere to go if a one-to-one relationship between the nine line segments and the nine dominos is desired. But what happens if the motif makes a U-turn and covers the same domino twice? Because the motif and covering are rotatable, the path will pass back over itself

Figure 6: “Filagree from Eleven Dominos” 2023 (Giclée print, 60” wide). A rotatable domino-filling curve approximation (to level 4) superimposed on its loop-closed fractal interior.

perfectly, regardless of the level of recursive detail. Thus the path will not look piecewise-connected (see the upper left or lower right corners), even though mathematically and programmatically it still is.

With such a U-turn allowed, the space-filling motif can continue left-up, left-up (through the central domino), and left-up again, where it can make its second (symmetric) U-turn, then find its way to the upper right corner of the covering. The rotatable motif is now eleven line segments long, rather than nine. But in the areas where it fills a domino twice in opposite directions, depending on which side of the path is “inside” and which “outside,” the colored-in foreground or background vanishes. Large-scale connected parts emerge,

The Art of Space-Filling Domino Curves

with a self-negative, self-similar, eventually fractal boundary that would be created with a seven-segment, non-space-filling motif that deletes the U-turns, skipping the two corner domino tiles altogether. But when the “filagree” of the space-filling approximation path is superimposed, as in Figure 6, there’s a lovely synthesis of intimately related homogeneous and emergent hierarchical structure. The filagree path’s self-contact divides its world up into various shapes and sizes, in a way the feels like a tiling of some kind but isn’t visually. Yet underneath the hood, it is structurally nothing more than a “threaded” order- $3^4=$ order-81 domino covering.

Over-Filling Motifs with Crossovers

The second way to extend the idea of a motif is illustrated in Figure 7. The underlying order-3 covering is the mirror image of the one in Figure 6. But notice that when a motif must travel from lower left to upper right

Figure 7: An overfilling, self-crossing, domino-filling curve approximation path, colored on one side.

of the covering, then a motif for the covering’s mirror image will be a distinct and different solution. The mirror symmetry is not the same as the rotational symmetry. In its struggle to find its way from the lower left to the upper right, the motif path can only succeed when it is permitted to traverse the lower left and the upper right domino a second time. The motif shown is the only solution, again using eleven line segments instead of nine. But this time, the motif crosses over itself in mirrored form. This means there won’t be the same cancellation of interior/exterior area as occurs when U-turns are used. The result after applying recursive edge-replacement stages is a path that criss-crosses over itself in certain places, creating interesting and Islamic-like hierarchical patterns, here rotationally symmetric about the center of the subdivided domino.

One can combine both U-turns and crossovers in overfilling motifs in the service of quite rich and aesthetically pleasing art, as shown in Figure 8 (see also Figure 12, left), in which the denser crossover areas of the filagree occur at four recursive levels of detail, drawing the eye to the visual complexity created. The more vertical crossover areas are in visual tension with the more horizontal background fractal interior.

Almost Space-Filling Motifs

A motif needn’t be space-filling or even rotatable to make for intriguing designs arising from the same recursive, edge-replacement process. Figure 9 shows an approximation to an almost-filling, rotatable domino curve based on leaving two corner dominos out of the order-5 motif’s path altogether (see also Figure 12).

McKenna

Figure 8: “Intricate Archipelago,” 2023. An order-4, self-negative, overfilling (U-turning and crossover), domino-filling curve approximation path, colored on one side.

Figure 9: “Two Way Street,” 2023. An order-5, self-negative, overfilling and underfilling, self-crossing, almost domino-filling curve approximation path, colored on one side.

The Art of Space-Filling Domino Curves

Figure 10 shows another self-negative piece I’ve done, where dominos near the center are removed. And again, there is an Islamic feel, see, e.g., [5], to all the recursive crossover areas, albeit with more irregularity. Figure 10: “Two To Tangle,” 2023. An order-5, overfilling, self-crossing, almost domino-filling curve approximation path, colored on one side.

Motifs with Direction-Reversing Loops and Coincident Segments

Motifs with paths that cross each other at domino corners form loops that locally reverse the path fill parity. If a motif path segment directionally coincides with a previous one without a U-turn, the effect will be the same as a U-turn: area-filling will cancel out, even if the motif is not rotatable. Figure 11 relies on an order-5,

Figure 11: “A/symmetric Carpet,” 2023 (three recursive levels, non-rotatable).

McKenna

non-rotatable motif (Figure 12, right) with a loop, two directionally coincident segments, with a missing domino in a symmetric position to the two. The result at the third recursive level seems rotatable (but is not) and is akin to a recursive fractal Sierpinski carpet, but with a much richer, completely deterministic structure.

Figure 12: The motifs, all found manually, for the domino curves in Figures 8, 9, 10, and 11, feature U-turns, crossovers, under-filling, and a loop (indicated with a circle) permitting two same-direction (non-U-turn) segments placed symmetrically w/r/t the one missing domino.

Summary and Conclusions

Self-similar order- $n$ domino coverings form a combinatorially explosive space, within which is a rarified sub-space of motifs of recursively built paths and, in the iterative limit, their continuous fractal curves, all generalizations of the original Peano Curve. One can find such motifs manually or by automated enumeration. Rotational symmetry combined with filling to one side, supports visually intriguing, abstract geometric art.

Generalized motifs with U-turns, crossovers, under- or over-filling, and/or loops relax an otherwise highly constrained space of solutions, thereby enriching the medium of domino coverings for finding interesting self-similar geometric designs. The size of any combinatorial space of solutions means one can make aesthetic choices, as well as mathematical ones. The colors one uses, and other graphic properties such as line thickness or shading, are separate issues that can enhance or detract from any eventual work of art.

For large $n$ , constructive enumeration algorithms searching combinatorially explosive spaces such as these can take an arbitrarily large amount of time just to find even a first solution. Above order-5 or perhaps order-6, it will likely be necessary to encode further constraints into enumeration algorithms to make a search of the space for interesting coverings and motifs possible. Alternatively, finding motifs using simulated annealing, AI, or other non-deterministic algorithms might prove productive.

The motifs for domino curves, and the algorithmic machinery for drawing them, are a medium for experimentation and play, in the service of pleasing the eye with tensions between symmetry and asymmetry, structure and texture, foreground and background, and hierarchy and homogeneity.

References

[1] S. W. Golumb. “Replicating Figures in the Plane.” Mathematical Gazette, 48, No. 366, Dec. 1964. [2] D. McKenna. “Designing Symmetric Peano Curve Tiling Patterns with Escher-esque Foreground/Background Ambiguity.” Bridges Conference Proceedings. 2008, pp. 123-130. https://archive.bridgesmathart.org/2008/bridges2008-123.. [3] D. McKenna. “Fibbinary Zippers in a Monoid of Toroidal Hamiltonian Cycles that Generate Hilbert-style Square-Filling Curves.” Enumerative Combinatorics and Applications, 2:2, Article S2R13 (2022). https://ecajournal.kms-ks.org/Volume2022/ECA2022_S2A13.pdf (journal mirror site). [4] G. Peano. “Sur Une Courbe Qui Remplit Toute Une Aire Plaine.” Math. Annalen 36 (1890), 157-160. [5] Shutterstock. “Islamic Lattice Photos.” 2024. https://www.shutterstock.com/search/islamic-lattice [6] N. Sloane. Online Encyclopedia of Integer Sequences. https://oeis.org/A099390.