The 7 Curve, Carpets, Quilts, and Other Asymmetric, Square-Filling, Threaded Tile Designs

Year: 2007 Authors: Douglas McKenna

Core claim

Corner-to-center asymmetric threading on square dissections produces many self-avoiding generators, with combinatorial counts varying sharply by order and offering aesthetic choice.

Topics

space-filling curves, square dissections, threaded tile designs, combinatorial enumeration

Domains

fractal geometry, combinatorics, tiling theory, self-avoiding paths, mathematical art, quilts, carpets, tile patterns

Methods

recursive generator construction, computer enumeration, uniform n×n dissections, visual pattern selection

Media

square tiles, giclée print, computer-generated images, tile designs

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.

The 7 Curve, Carpets, Quilts, and Other Asymmetric, Square-Filling, Threaded Tile Designs

Douglas McKenna $\bullet$ Mathemæsthetics, Inc. 1140 Linden Ave. $\bullet$ Boulder $\bullet$ Colorado $\bullet$ 80304 doug@mathemæsthetics.com

07.07.07

Abstract

Visually intriguing tiling patterns arise from an asymmetric “threading” technique for constructing space-filling curves in the square. The method uses four square tiles in varying or uniform sizes, each the mirror or negative image of a single directed line segment. On varying size “quilt” dissections, the simplest pattern, built of just seven threaded tiles, is as fundamental a construction as the classic Peano or Hilbert Curves. For uniform $n\times n$ tilings, a computer enumeration finds $0,0,0,6,5,366,0,4110384,\dots$ of these special threaded tile designs for $1\le n\le 8$. The combinatoric explosion of possible patterns permits one to pick and choose among them using æsthetic criteria.

Introduction

Classic space-filling curve constructions dissect a square tile into a set of smaller square tiles, and then spatially “thread” a path through all of them in a geometrically self-referential manner. Limiting cases of these constructions eventually revolutionized the mathematical concept of a curve, and are now recognized as a certain kind of fractal. But initial, rough-detailed stages of these constructions are fascinating in their own right, both visually and combinatorially. I use them to create vibrant and intriguing, self-referential tiling patterns that can be further transformed or otherwise used in making mathematical art.

Threading the square asymmetrically

Like a variety of geometric figures, the square has a self-referential or recursive, property. It is a rep-tile [1], i.e., it can be subdivided, or dissected, into smaller squares, each of which has the same shape as the whole and which together, in various orientations, tile the whole. Because the sub-tiles are the same shape, the process can be repeated to any degree of detail desired. Space-filling curve constructions are based on “threading” these tiles with a path that orders them in sequence without skipping any tiles or using any of them more than once. The ordering must maintain threaded connectedness between spatially adjacent tiles.

Peano and Hilbert devised the first space-filling curve constructions (Figure 1, left and middle) [2]. Peano-style paths connect opposite corners of every square along a symmetric diagonal. Hilbert-style constructions are a little less symmetric: they connect adjacent corners along an edge. But there is one other elementary traversal strategy that serves to thread the sub-squares. It does so in a completely asymmetric manner: it connects a square’s corner to the center of one of the two opposite sides, and vice-versa. One can use these constructions to build tile designs. The more asymmetric the tile set, the more visually interesting the patterns become.

An asymmetric threading of a dissected square, connecting a corner with the center of an opposite side (and vice-versa), can occur in 16 possible ways: 4 rotations $\times$ 2 mirrorings $\times$ 2 threading

Figure 1: Left: Peano constructions from corner to opposite corner require only one rotatable tile. Middle: Hilbert constructions connect adjacent corners, and require two tiles. Right: 16 possible ways to traverse a square from corner to side or vice-versa, requiring four rotatable tiles.

directions. These 16 configurations are equivalent to four (rotatable) tiles (Figure 1, right bottom). Under various constraints an ordered sequence of tiles, each tile taken from these four, specifies a generator, i.e., a connected path $\to$ arrow head to arrow tail $\to$ that traverses all the sub-squares of the dissection. When recursively applied to themselves, generator paths build more complicated paths of increasing length that remain tiling patterns. In the (visually uninteresting, abstract) limit, they converge to fractal, space-filling curves that reach every point in the square.

Enumerating generators on uniform dissections

Only certain path shapes can generate a space-filling curve. Finding these constrained generator shapes is a combinatoric problem. The constraint of self-avoidance is particularly interesting for many reasons, both mathematical and visual. For instance, self-avoiding paths delineate connected (i.e. same-colored) areas that our visual system integrates into larger emergent shapes.

The simplest dissection strategy is to choose an integer $n\ge 1$ , and dissect a square region into $n^2$ sub-squares, arranged in an $n\times n$ array. This is a uniform dissection of order $n$ . The order 1 dissection is obviously a degenerate case. Neither the order 2 nor order 3 dissection supports a generator that travels from the lower left corner to the center of the top side. Unlike the $2\times 2$ Hilbert or $3\times 3$ Peano constructions in Figure 1, there is simply not enough freedom for a self-similar threading that connects corner to center, or center to corner.

Figure 2: Six locally self-avoiding threading patterns (generators) on the order 4 dissection.

On the order 4 dissection, however, one can easily find several solution generators by hand. Two of these were first described in [3]. Figure 2 shows all six locally self-avoiding generators,

as enumerated by computer. Figure 3 shows the first few construction stages that replace each of the 16 sub-squares of one generator (third from left) with a scaled, rotated, negated (i.e. white and black swapped), and/or mirrored copy of the generator itself.

Figure 3: Left: A generator for the order 4 dissection, and construction stages 2 and 3. Right: Pattern composed of the four tiles from Fig. 1 (without showing any grout lines) based on the third stage.

A computer enumeration of the order 5 dissection finds only five locally self-avoiding generators (Figure 4, top), one less than the number for order 4, even though the dissection has nine more sub-squares with which solutions can be built. The constrained nature of low odd orders is due, in part, to the fact that there are fewer ways to thread the final sub-square in an odd-order dissection than there are for even orders. The bottom of Figure 4 shows the result of using 25 copies of the rightmost generator of the five as a recursively arranged tiling design.

On the order 6 dissection, the expected combinatorial explosion of solutions begins. The computer finds 366 generators. Some solutions permit the eye to understand the underlying repetitive structure (Figure 5, left); others hide the $6\times 6$ -ness quite mysteriously (Figure 5, right).

Somewhat unexpectedly, the same computer enumeration algorithm finds that there are no locally self-avoiding generators on the order 7 dissection, even though the algorithm finds solutions for orders 8, 9, and 10. Preliminary partial enumeration finds no solutions for order 11 at the same time as it does find some for order 12. This evidence supports a conjecture that there are no solutions for orders 3, 7, 11, 15, …, i.e. when $(n-1)/2$ is odd.

A complete enumeration of the order 8 uniform dissection finds 4110384 locally self-avoiding generators from lower left corner to the center of the top side. Figure 6 shows a curve whose threading rendered as a tile design is quite pleasing, with an undulating, sinuous feel to larger areas

Figure 4: Top: Five locally self-avoiding generators for the order 5 uniform dissection. Bottom: Recursive tile design based on the rightmost of the five generators above, using its negative and mirror images also.

Figure 5: Two of the 366 constructions for the order 6 construction. Each pattern is made up of 36 copies of the generator or its negative. The underlying tiling is apparent on the left, but difficult to discern on the right.

that the eye integrates into shapes, with symmetric and asymmetric forms attracting the eye, and with positive and negative spaces composed of essentially the same shapes.

Figure 6: Left: One of 4,110,484 order 8 solutions. Right: 64 copies, arranged according to the original in either negative or positive, or right- or left-handed forms, rendered as a tiling. The border between black and white forms a continuous path, locally self-avoiding, but not globally due to inter-copy interactions.

Thus, computer enumeration finds that the number of possible shapes with which to build these tiling designs is $c_n=0,0,0,6,5,366,0,4110384,\dots$ for $1\le n\le 8$ . As they become more numerous, it becomes possible to pick and choose among them using aesthetic criteria.

Quilt dissections

If we relax the constraint that all square tiles be the same size, the space of solutions gets more interesting. Dissections into multi-sized squares have been called “quilts.” When adjacent subsquares have relative sizes differing by a factor of 2, combinatoric freedom increases somewhat, and simpler solutions become possible. This is because in uniform dissections, there are only two ways to proceed from the center of a sub-square’s side. But in certain quilt dissections, a segment can end at the center of a side of a larger square, with the choice of continuing in one of four ways from the corner of either of two smaller half-size squares.

The “Mrs. Perkins’ Quilt” series (Sloane’s A005670) [4] [5] describes certain heterogeneous dissections of the square of side $n$ . Some of these are suitable for supporting space-filling threadings; others are not. Because of the asymmetry of the traversal, when the spatial arrangement of the sub-squares in a dissection is also asymmetric, different orientations of that dissection must be considered distinct. Some orientations of a given dissection admit solutions, others don’t.

The 7 Curve

In [3], I described 10 simple space-filling curve generators that traverse, using the above tile threading technique, certain orientations of certain quilt dissections of a $4\times 4$ square into 10 subsquares, two of side 2, and eight of side 1. These ten solutions were enumerated by hand, and fall into three visual classes that I call “Quartets,” “Dances,” and “Treads.” At the time I thought they were the simplest such constructions. But there is a unique simpler construction whose generator requires fewer line segments.

Figures 7 show the dissection with the fewest sub-squares that supports a space-filling curve generator built using asymmetric corner-to-center diagonal line technique. Successive stages eventually fill the square completely. The dissection is one orientation of the fourth entry in the Mrs. Perkins’ Quilt sequence. For a canonical traversal from lower left to the top center, the dissection supports a generator only in the given orientation. Other than a non-distinct mirror image across a $45^{\circ }$ diagonal, no generators are possible for any other set of three $2\times 2$ and four $1\times 1$ sub-squares that dissect a $4\times 4$ square.

Figure 7: Top: Construction stages 0 to 6 of the 7 Curve, which in the limit, fills the square. Its generator is the second from the left. Bottom: The same stages, as tile designs with tiles of different sizes.

The only two simpler quilt dissections with fewer sub-squares are the uniform $2\times 2$ dissection, and the one that divides the square into 6 sub-squares, one $2\times 2$ and five $1\times 1$ . Neither supports generators using corner-to-center asymmetric diagonal threading. The 7 Curve is thus as fundamental a square-filling construction as the original Peano or Hilbert Curves, which use the two other square traversal strategies, shown in Figure 1.

Because the 7 Curve’s generator replaces a single more-vertical-than-horizontal segment with seven more-horizontal-than-vertical segments, successive construction stages alternate between strong vertical and horizontal visual elements.

The 7 Curve’s seven-segment generator has an interesting point of symmetry at the sole intersection of the middle segment of the generator and the line segment at the previous stage the generator replaces (Figure 7, below). That intersection occurs within the only interior sub-square of the dissection, and within the only interior sub-sub-square of its own dissection, ad infinitum. If the generator traverses a unit square from $(0,0)$ up to $(\frac{1}{2},1)$ , the intersection point is $(\frac{1}{3},\frac{2}{3})$ . This point is also exactly two-thirds of the linear distance along the generator as measured from the origin. If one cuts the generator at this point, the path divides into two geometrically similar pieces, each in the shape of a rotated numeral “7” (avec serif), one twice the size of the other. In the limit, this single point “divides” the square into two geometrically similar pieces, one a quarter the area of

Figure 7: The 7 Curve’s seven-segment generator is “bisectable” at a special fixed point into two similar, rotated, 7-shaped pieces, one half the size of the other. The limit curve traverses the black and gray areas (which will be geometrically similar) of the unit square on either “side” of the point $\left(\frac{1}{3},\frac{2}{3}\right)$ .

the other (Figure 7, right). The space-filling curve fills $\frac{4}{5}$ of the square’s area (black) before filling the remaining $\frac{1}{5}$ (gray) as it makes its continuous traversal from the origin to the center of the top.

Threading a carpet

After the Quartets, Dances, and Treads of [3], and the 7 Curve, one remaining interesting quilt dissection of the $4\times 4$ square requires one $2\times 2$ sub-square, and twelve $1\times 1$ sub-squares, arranged in various ways. One arrangement—placing the $2\times 2$ sub-square in the center—is highly symmetric. It supports two related generators whose differently converging parts are distributed according to the geometry of a variant of the fractal Sierpinski carpet [6]. Figure 8 shows one of them. Interestingly, stage 2 is a completely self-avoiding threading, although later stages are not.

Figure 8: Stages 1 through 4 of an asymmetric space-filling traversal of a symmetric dissection related to a Sierpinski carpet fractal.

One can round off the corners to guarantee that the curve path is everywhere self-avoiding. Even though it creates a pattern that is no longer strictly a tile design, the path’s self-avoidance significantly increases the overall visual intrigue. A self-avoiding path divides its two-dimensional world into two connected parts, but the space-filling generation process guarantees that locally repeated patterns will appear in both positive and negative forms, yielding a nice interplay between foreground and background. The asymmetry of the construction also means an interplay between right- and left-handed patterns. Figure 9 is a rendition, based on the 13-dissection discussed above.

Figure 9: “Thirteenski” (giclée print, © 2006), based on a $4\times 4$ carpet threading. The tile pattern’s path has been manipulated so that the colored area is simply-connected, imparting a more organic, carved look to it.

Conclusion

The asymmetric corner-to-center threading technique for building space-filling curve generators that in the limit continuously fill just a square region results in a great many visually pleasing patterns that can be built as tile designs. The order, $n$ , of a dissection is a parametric “knob” that governs combinatoric freedom, thereby opening a window into a fascinating visual space subject to interesting constraints. The smaller $n$ is, the more platonically beautiful the patterns become due to the higher degree of constraint. But as $n$ increases, the combinatoric explosion of possible generators means one can pick and choose amongst them using aesthetic (or other) criteria. As a medium, these threaded tile patterns are in and of themselves … mathematical art.

References

[1] Golomb, S., “Replicating figures in the plane”, Math. Gazette, Vol. XLVIII, No. 366 (1964). [2] Sagan, H., Space-Filling Curves, Springer-Verlag (1994), ch. 1-3. [3] McKenna, D. M., “Asymmetry vs. symmetry in a new class of space-filling curves”, Conf. Proc. Bridges Math. Connections in Art, Music, and Science (2006), 371-378. [4] Sloane, N. A. J., Handbook of Integer Sequences. Academic Press, NY (1973). [5] Conway, J. H. “Mrs. Perkins’s Quilt,” Proc. Camb. Phil. Soc. 60 (1964), 363-368. [6] Mandelbrot, B. B., The Fractal Geometry of Nature (1982), 144.