Tendril Motifs for Space-Filling, Half-Domino Curves

Year: 2016 Authors: Douglas M. McKenna

Core claim

Self-avoiding tendril motifs can be recursively arranged into half-domino space-filling curves with constrained parity, symmetry, and boundary behavior.

Topics

space-filling curves, Hamiltonian paths, self-similarity, tiling motifs, aesthetic patterning

Domains

graph theory, combinatorics, topology, fractal dimension, ornamental design, fabric pattern, aesthetic exploration, visual symmetry

Methods

recursive construction, orientation and parity analysis, Jordan Curve Theorem argument, computer backtrack search

Media

square subdivisions, domino prototiles, line drawings, computer-generated motifs

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

Tendril Motifs for Space-Filling, Half-Domino Curves

Douglas M. McKenna

Mathemæsthetics, Inc. • DMCK Designs, LLC

Boulder, Colorado $\cdot$ doug@mathemaesthetics.com

Abstract

An order- $n$ half-domino space-filling curve converges to a tile of area $n^2$ , two copies of which form the congruent halves of an $n\times 2n$ domino. The order-2 Hilbert Curve and its square-filling order- $n$ generalizations are special cases where the length of the cut dividing the halves is $n$ . But in a more general case, the division between the two congruent halves is infinitely long, self-similar, yet almost-everywhere linear. The most extremely convoluted half-domino tiles are generated by motifs that are double-stranded, self-avoiding tendrils. These patterns form an interesting medium for mathematical, biological, ornamental, tiling, fabric pattern, and aesthetic exploration.

Introduction. This paper explains how the seemingly arbitrary tendril pattern in Fig. 0 can be the basis for a recursive space-filling curve with a self-similar, infinitely long, nonfractal boundary that is both eye-catchingly beautiful and almost-everywhere linear.

I recently collaborated with a group of researchers who had earlier posited that self-similar, space-filling curve constructions might model compactly folded DNA [1]. Our group relied upon a new theorem that relates the fractal dimension of the boundary of a self-similar space-filling curve to the distribution of the lengths of “near-loops” formed by the path’s closest contacts with itself. I came up with a simple and elegant perturbation technique, as applied to generalized Hilbert Curves, so as to create new space-filling curves with which to experimentally confirm the theorem. In the limit, these curves are tiles with (handed) p4 wallpaper symmetry and nowhere-differentiable boundaries whose fractal dimension can

Figure 0

be discretely tuned—in theory if not in practice—arbitrarily close to 2.0. Remarkably, it’s possible for the limit set of the boundaries of these space-filling-curve sequences to be space-filling curves themselves [5].

But as shown below, p4 symmetry is not necessary to construct square-based space-filling curves with Hilbert-style connection geometry. It turns out that the Hilbert Curve and its order- $n$ , square-filling generalizations can be considered degenerate cases of what I call half-domino curves.

The domino path constraint. Consider an $n\times n$ square, subdivided into $n^2$ unit sub-squares. Choose a sequence of edge-adjacent sub-squares starting at the lower left sub-square and ending at the lower right sub-square, such that each of the $n^2$ sub-squares is included in the sequence exactly once (the “Greek key tour” sequence A0000538 [4] counts these sequences). This is equivalent to a Hamiltonian path of length $n^2-1$ (from sub-square center to sub-square center) on the edge-adjacency graph of the subdivision. Each such path is also a motif that can be used to recursively build a sequence of longer self-avoiding paths formed from $n^2$ scaled-by $-\frac{1}{n}$ copies of the motif, appropriately oriented and sequentially connected. The limit of the sequence of exponentially lengthening paths, constrained within the confines of the initial square, and never farther than any \epsilon > 0 (no matter how small) from any given point in the square, is a space-filling curve. Fig. 1 shows the motif and the first two approximation paths of an order-8, generalized Hilbert Curve.

Each motif travels via sub-squares from one corner to an adjacent corner (large dot pair, left, Fig. 1) of the square subdivision. Therefore, one can place a scaled motif into any sub-square in one of four orientations (small dot pairs). It is straightforward to prove that, for any given motif path, there is only one way to assign

McKenna

Figure 1: Left: An order-8 motif, showing implicitly oriented sub-squares. Middle, Right: The same motif applied to itself recursively according to those orientations to create a second and third approximation to a space-filling curve (if PDF, you can zoom in to see the $64^3-1$ details).

orientations to sub-squares. ${}^1$ Beyond the four orientations, there is also a parity condition that necessarily arises when connecting adjacent motif copies at corner sub-squares: the sequence of sub-sub-squares in each component motif’s path must be followed in either forward or backward order. Because these Hamiltonian paths are self-avoiding, a sub-square’s parity also declares which side of any given motif (in whatever orientation) can be called outside or inside, depending (arbitrarily) on whether one were to close the open-ended path into a self-avoiding loop in a clockwise or counterclockwise manner. It turns out there is a linkage, though, between the four orientations and the two parities: sub-squares with dots oriented vertically must be traversed backward whereas those with dot pairs oriented horizontally must be traversed forward.

Within the square subdivision, choose any two sub-squares sharing an edge, not necessarily sequentially along any path. Each can be in one of the four orientations. So, for any order- $n$ motif (in Fig. 2 it’s an order-6 motif), consider the complete $4\times 4$ matrix of spatially adjacent, pair orientation combinations. Because we know that individual motifs in sub-squares are eventually all connected into a single self-avoiding path at the next recursive stage, certain combinations (circled) create impossible parity situations. Why? Because the Jordan Curve Theorem requires that if two parts of the plane are of opposite inside/outside parity, the self-avoiding path must separate them. But no path segments are there to do so.

Figure 2: All possible pairs of spacially adjacent, oriented motifs whose sub-squares share an edge. Circled pairs create impossible parity combinations.

The matrix’s remaining legal combinations form a pair of sub-matrixes, $3\times 3$ and $1\times 1$ . As the sole legal entry in its row and column, the $1\times 1$ sub-matrix (Fig. 2, lower right top:top entry, highlighted), immediately proves that—regardless of parity—the top edge of an oriented motif can only ever be adjacent to another copy’s top edge, rotated $180^{\circ }$ (the rest of this paper explores the consequences of this $1\times 1$ matching rule). Furthermore, this constraint does not depend on any global shape of the collection of $n^2$ sub-squares.

Tendril Motifs for Space-Filling, Half-Domino Curves

Perturbed prototiles. Knowing that the top row of the order- $n$ subdivision can only ever be adjacent to an upside-down copy of itself during the process of recursive motif replication, we can carefully rearrange some of the sub-squares along the top, to create a half-domino prototile, still composed of $n^2$ sub-squares, characterized by one indentation and one “outdentation,” each having the same shaped boundary. But if we are to find a motif for that prototile, we must guarantee that the perturbed set of $n^2$ sub-squares still has a dual edge-adjacency graph that admits a Hamiltonian solution (e.g., at the very least, every sub-square must still have two or more edge-adjacent neighbors). So consider, for example, carving a $2\times 2$ indentation out of the right side of the top of the order-8 subdivision, and transferring the sub-square “material”, as an antisymmetric outdentation, to the top of the left side (Fig. 3). There will be fewer Hamiltonian path motifs that will work for this prototile compared with the $n\times n$ subdivision, but there will still be a great many of them. And in every one, upon recursive replication, a top:top pair will then mate perfectly, creating a $1\times 2$ subdomino in some orientation. We use the term self-negative to describe the perturbation: whatever its shape, it has a central point of symmetry so as to fit with itself under $180^{\circ }$ rotation. For generalized Peano curves based on a diagonal connection geometry, “self-negative” is with respect to a point of rotational symmetry at a square subdivision’s center [3]; here, where we’re using a Hilbert connection geometry, it is with respect to the center of a domino (the top edge of the original square subdivision).

Figure 3: An order-8 prototile, with an indentation and outdentation along the top. The sample motif recursively builds a space-filling curve with an infinitely long, non-fractal, self-similar, almost-everywhere linear border (as before, if PDF, zoom in to see 262143 line segments).

The simplest half-domino curves. The freedom to perturb the subdivision starts at $n=4$ . Fig. 4 shows motifs for all the possible prototiles, along with two copies exactly covering the entire domino. The left two prototiles support more than one Hamiltonian motif. The rightmost two are so constrained that only one distinct (i.e., ignoring mirror images) motif is possible.

Almost everywhere linear boundaries. The borders of these half-domino curves look fractal, but they’re not. A fractal dimension $D$ can be determined using the box-counting method. Call $N_k$ the number of boxes of size $\frac{1}{n^k}$ at stage $k$ needed to cover the border. If the exponential growth rate of $N_k$ is greater than the exponential growth rate of the number of ever-tinier boxes that would cover a straight line, then D > 1.0 (because the dimension $D$ is the ratio of the two exponents).

Figure 4: Bottom: The four simplest half-domino curve motifs ( $k=1$ ). Top: A pair of ( $k=3$ ) approximations, exactly covering a domino.

McKenna

But with the prototile in Fig. 3, at each recursive stage $k$ the box count $H_k$ covering horizontal portions of the border increases by a factor of $n=8$ while the box size decreases by 8, i.e., there’s no change in total horizontal length. The vertical count $V_k$ is $8H_{k-1}+8V_{k-1}$ , because once a vertical length is introduced into the border, it also remains constant. The border’s growth in length at stage $k$ arises solely from horizontal segments at stage $k-1$ introducing new vertical edges. The total length diverges, but the exponential rate of growth of total boxes covering the boundary is the same as the rate the boxes decrease in size. Thus, in the limit, the dimension of the hierarchically self-similar border that divides the two domino halves is just 1.0. The boundary is not just almost-everywhere linear—it’s almost-everywhere vertical! This is reminiscent of the Devil’s Staircase (the integral of the Cantor Set) [2], although in the stair’s case, its length is finite.

Digging deeper. Nothing prevents digging out and self-negatively rearranging more sub-squares. One cannot, however, dig all the way to the bottom of the subdivision—the prototile must stay simply connected to permit a Hamiltonian path as a motif. But because the motif only needs to travel one way, (red arrows, either forward or backward), a single bottom row of sub-squares still allows solutions. Figs. 5 and 6 show two even more towering examples. Due to the thinness of the bottom row, in the limit these half-domino tiles have cut-points along their bottom edges (remove a cut-point and the tile becomes disconnected).

Figure 5: Another half-domino space-filling curve, reaching in the left half a height of $y=16$ at a countable number of points, with corresponding cut-points at $y=0$ along the bottom right half

In Fig. 6 the motif first rises through a minimally narrow channel comprising pairs of sub-squares (dominos) that form a tendril, a word borrowed from biology to connote both thinness and growth. Each tendril either branches into further tendrils or ends at a tip where the motif’s path makes a U-turn. The Hamiltonian path travels to the tendril’s end or exit, eventually turns around, then travels back through the tendril’s other half. The initial vertical tendril in Fig. 6 branches into three smaller tendrils (inside the shaded area), like fingers.

Figure 6: A top-heavy half-domino space-filling curve

Tendril Motifs for Space-Filling, Half-Domino Curves

Self-avoiding tendrils. The visual complexity of the boundary of the half-domino space filling curve rises and falls with the ratio of the prototile’s perimeter length to its interior area. But for a given $n$ the interior area $n^2$ remains constant. So when every (or the) tendril in a motif is surrounded by space, the ratio is maximized. Because the tendrils need only reach half of the domino’s sub-squares, there is “wiggle-room” for tendrils to be self-avoiding. Fig. 7 shows another half-domino curve whose motif is one large self-avoiding tendril, and two partially adjacent tendrils in the lower right. This motif also shows that a tendril can make turns.

Figure 7: Top: An almost-single tendril order-8 motif, and its next two space-filling curve approximations. Bottom: A (sideways) domino “throw rug” built from two congruent half-domino curves, each filling the background interstices of the other (if PDF, zoom in to see myriad details).

Figure 8: A maximally long, self-avoiding, order-8 tendril motif, approximation stages for $k=1,2,3$

Fig. 8 shows a wholly self-avoiding, maximally long, single-tendril motif. But something new occurs here. The limiting space-filling curve, which is a tile, is no longer simply connected—it converges to a gasket. The green arrow on the right indicates a point of self-contact (at normalized (.75, .25)) that occurs in the limit set. The path at stage $k$ converges on itself from both below and above to points on, e.g., the lines $y=1/8^{k-1}$ .

McKenna

This “in turn” suggests an infinite series of increasingly tightly wound motifs and their limiting half-domino tiles, as shown in Fig. 9. For obvious reasons, I’ve nicknamed these paper clip curves. Each approximation path of the $n$ th motif applied recursively to itself $k$ times remains a self-avoiding path traversing $n^{2k}$ sub-sub-squares. Holding $n$ constant and letting $k\to \infty$ , the paths converge to a space-filling curve, which itself is a bounded area in the plane of size $n^2$ because exactly two copies form congruent halves of an $n\times 2n$ domino. Interestingly, if one normalizes the original domino to $1\times 2$ , then each order- $n$ half-domino curve in this infinite sequence has, by symmetry, area 1. Yet the set to which this infinite sequence of constant-area objects converges as $n\to \infty$ , the entire domino, has area 2. Every point inside the domino is approached by some sequence of points, $p_n$ , each point itself a member of the area converged to by the $n$ th paper clip curve. All the equal positive and negative space becomes infinitely thin. Then, in the limit, the negative space vanishes just as the positive space reaches every point of the domino.

Figure 9: Top: First through sixth motifs ( $k=1$ ) of an infinite sequence of paper-clip curves. Bottom: The next ( $k=2$ ) recursive stage (if PDF, zoom in for details).

Branching motifs. If we allow tendrils to branch, many more solutions become possible. As the order $n$ increases there is a combinatorial explosion of motifs, albeit still constrained to be self-negative with respect to the domino’s center, as Fig. 10 shows.

Figure 10: A branching half-domino curve motif, and its next two recursive approximation stages

Tendril Motifs for Space-Filling, Half-Domino Curves

The yin and yang beauty of half-domino tendril curves. The leap in the size of the solution space means one can explore it and make aesthetic decisions on elegance of form, what that form is reminiscent of, and all the other aspects of what a piece of art/design, as a human choice, communicates. For instance, my piece “A Unit Domino” (Bridges 2015 art show) is based on a minimally branching, double-spiral order-60 motif.

Fig. 11 shows the result of applying the order-12 motif of Fig. 0 to itself recursively (there are exactly $12^2$ connected copies), with a mated pair of half-domino curve approximations creating a design reminiscent, perhaps, of a Persian doorway or the map of an intimate self-similar souk with many inner sanctums, or an Arabian (magic) carpet. The stringent tendril self-avoidance constraint has been relaxed so as to fill larger areas, preventing convergence to a gasket. The resulting pattern is more pleasing to the eye than usual because of a balance and tension between symmetry and asymmetry. It has a more soft and less frenetic feeling with respect to the border’s visual complexity, which is relegated to the domino’s interior by the mated pair. All repeated motifs pointing upward are self-negative w/r/t those pointing downward. This enables the two halves to mesh at every recursive level. There is a nice balance between clean vertical linearity and convoluted horizontal complexity, even though there is recursive self-similarity throughout.

Figure 11: Left: Second approximation of the motif in Figure 0. Right: A pair of them covering a domino.

McKenna

Using computer backtrack search techniques, I have enumerated over 40,000 non-branching tendril motifs—nearly all partially self-avoiding and self-contacting—for the order-12 subdivision of the domino. Each is a unique Hamiltonian solution for some prototile, but the prototile boundaries tend to be very duplicative—there are far fewer unique self-negative boundaries. Further work using a different enumeration strategy will help cull these duplicates, perhaps permitting productive searches of higher orders of $n$ . I have examined about half of these order-12 motifs, looking for forms that I find to be elegant, intriguing, balanced, etc. Fig. 12 shows two such self-negative designs, both for $k=2$ , based on using two dominos (four half-dominos) to fill a square. The pattern on the left reminds me of Native American Zuni rug weaving patterns.

It’s pleasantly remarkable that measure theory and the study of the continuum might bear on aesthetics!

Figure 12: Using pairs of self-negative, order-12, half-domino curves—drawn with lines the same thickness as sub-squares so as to hide the actual paths—to color in prototiles at stage $k=2$

Conclusions. As the subdivision order $n$ increases, a combinatorial space for self-negatively constrained, space-filling half-domino curve motifs and their prototiles opens its doors. Within that space, one can explore for patterns using aesthetic considerations such as elegance of form, balance, beauty, visual reference and meaning, or other criteria. And not every infinitely long and infinitely detailed, finitely bounded, self-similar, and infinitely zoomable object is (technically speaking) a fractal.

References

[1] LIEBERMAN-AIDEN, E., VAN BERKUM, N. L., et al., “Comprehensive Mapping of Long-Range Interactions Reveals Folding Principles of the Human Genome,” Science, 326, p. 289 (Oct. 9, 2009). [2] MANDELBROT, B. B., The Fractal Geometry of Nature (illustrated in part by McKenna, D. M.), Plate 83 (1982), Freeman. [3] MCKENNA, D. M., “Designing Symmetric Peano Curve Tiling Patterns with Escher-esque Foreground/Background Ambiguity,” Proc. of Bridges Conf. (2008). [4] SLOANE, N. J. A., The On-Line Encyclopedia of Integer Sequences, www.oeis.org/search?q=A000532 (as of 4/8/16, an exponential date!). [5] SANBORN, A. L., Rao, S. S. P., et al (including McKenna, D. M.), “Chromatin extrusion explains key features of loop and domain formation in wild-type and engineered genomes,” Proceedings of the National Academy of Sciences, 112, p. 47 (Nov. 24, 2015).