Lattice Labyrinth Tessellations

Year: 2014 Authors: David Mitchell

Core claim

A missing-links algorithm constructs infinitely many lattice labyrinth families on square and triangular lattices, governed by simple Diophantine conditions and symmetry constraints.

Topics

tessellation families, lattice graphs, symmetry, Diophantine conditions, missing-links algorithm

Domains

graph theory, tiling theory, number theory, Diophantine equations, Hamiltonian cycles, pattern design, logo design, Escher-style tessellations

Methods

constructive algorithm, parameter classification, lattice-link analysis, family enumeration, symmetry analysis

Media

square lattice, triangular lattice, polyominoes, polyiamonds, figures and tables

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.

Proceedings of Bridges 2014: Mathematics, Music, Art, Architecture, Culture

Lattice Labyrinth Tessellations

David Mitchell Scarthin Books, Scarthin, Cromford, Derbyshire DE4 3QF, UK

Abstract

Repeating graphs whose lattice-link edges connect all the points of the square or of the triangular lattice can form the boundaries of symmetrical monohedral tessellations (tilings), termed lattice labyrinths. Requiring all lattice points to be connected implies that the prototiles of the tessellations are slim polyominoes and polyiamonds made up of corridors just one square or triangle wide, enclosing no lattice points and having boundaries of maximum length given their area. There is no upper bound to the area of the prototiles of the several infinitely populous families of lattice labyrinth tessellations. Lower-order examples invite Escherization and are a fertile source of logos. Despite being homeomorphic to the chessboard, honeycomb or other simple tilings, higher-order labyrinths are beguilingly intricate and the maximized boundary length and interpenetration of the prototiles may allow technical applications.

Lattice Labyrinth Tessellations Constructed on the Square Lattice

In layman’s terms, the square lattice is graph paper with dots. Each dot, or lattice point, is connected to its four nearest neighbors by lattice links, which form the boundaries of square tiles. The tiles tessellate to cover the Euclidean plain regularly without gaps. Examples of this tessellation include the chessboard and the layout of city blocks separated by a gridiron street plan. As part of my Ph.D. research [6] I explored routing strategies on the gridiron. Every intersection, or lattice point, is ultimately connected to every other by the street pattern, comprising an infinite graph in which every lattice link is an edge. Might it be possible to connect all the lattice points by a repetitive infinite graph without using all the lattice links? I soon found two graphs that achieve this, shown in Figure 1. The lattice links used to connect the lattice points are the edges of a tessellation graph forming the boundaries of the prototiles of each tessellation; a five-square cross and the ancient swastika symbol.

Figure 1: The basic tessellation and lowest-order Chinese lattice labyrinth tessellations.

The three tessellations of Figure 1 are closely related. Each is monohedral, made up of just one shape. They are homeomorphic, topologically equivalent to each other, inter-convertible by continuous stretching and scaling. The tessellation graphs which form the boundaries of the shapes

Mitchell

connect every lattice point to every other. This means that the polyominoes which make up the tessellating shapes are slim, never more than one square wide. A subset of the lattice points (all of them in the case of the chessboard) lie at the corners of the prototiles of the tessellation, which I call supertiles (just one tile in the chessboard case) and are the only lattice points where four lattice links of the tessellation graph meet. I call these the superlattice points. All three tessellations exhibit the same pattern of rotational symmetry axes – two distinct families of tetrads ( $90^{\mathrm{O}}$ rotation leaves the pattern unchanged) and one family of dyads ( $180^{\mathrm{O}}$ rotation leaves the pattern unchanged). In J.H. Conway’s notation [2], the tessellations all display 442 rotational symmetry. The chessboard and crosses tessellations also display mirror symmetry, which I am ignoring.

It is natural to enquire whether the three tessellations of Figure 1 are the lowest order members of a larger general family sharing the above properties. Yes they are - I call them the Chinese lattice labyrinths in honor of Dye’s classic book of traditional patterns [4]. Let’s narrow down our search for further family members. Firstly, note that in the crosses and swastikas tessellations, the superlattice points themselves form a square lattice, larger than and inclined to the original lattice. This superlattice is specified by the separation parameters (a,b), counting along the x and y axes respectively, which are (1,2) in the crosses case and (3,2) in the swastikas case. The squares of the superlattice are in one-to-one correspondence with the supertiles of the tessellation, so the area of each supertile must equal ${\mathbf{a}}^2+{\mathbf{b}}^2$ in the general case, 5 and 13 squares in our two examples. This narrows the search to supertile areas which are the sum of two squares [3]. Secondly, each supertile has a central square plus four arms of identical shape (of zero area in the chessboard case), so the area of a supertile must be of the form $1+4\mathbf{m}$ , where $\mathbf{m}$ is zero or a positive integer. Table 1 shows the lowest-order cases satisfying the integer-solutions-only Diophantine equation ${\mathbf{a}}^2+{\mathbf{b}}^2=1+4\mathbf{m}$ .

Table 1: Parameters of the lowest-order Chinese lattice labyrinth tessellations.

The Diophantine equation implies that one of the parameters $\mathbf{a}$ and $\mathbf{b}$ must be odd and the other even (we can let $\mathbf{a}$ be the odd parameter). This satisfying result is only a necessary condition for higher-order examples of Chinese lattice labyrinth tessellations to actually exist. The sufficient condition I propose is a general algorithm for constructing a family member tessellation adaptable to any set of parameters $(\mathbf{a},\mathbf{b})$ , the elegant and powerful missing-links algorithm. The tessellation graph bounding the supertiles comprises all four lattice links intersecting at each superlattice point but only two of the four links intersecting at every other lattice point. The edges of the missing-links graph are just these unused two lattice links intersecting at each lattice point except for the superlattice points. Together they comprise an

Lattice Labyrinth Tessellations

infinite set of closed-loop Hamiltonian cycles [1] visiting no lattice point vertex more than once. Figure 2 shows examples of tessellations, each with its elegantly simple and easily described missing-links graph.

Fig 2: Examples of Chinese lattice labyrinths showing the corresponding missing-links graphs.

Fukuda et al [5] have developed a computerized procedure for generating all polyominoes and polyiamonds that will tessellate symmetrically, displaying results for $n$ -ominoes up to $n=9$ . Their procedure will, I believe, encounter time-problems for high-order cases, which are likely to become intractable. There are already more than $10^{13}$ polyomino shapes to choose from when searching for Chinese labyrinth (5,12). The restriction to tessellations only of slim polyominoes leads to the missing-link algorithm, the labor of which is only linearly dependent on the order of the polyomino. Missing-links graphs are easy to construct whereas the convolutions of the tessellation graphs resist comprehensive categorization. The missing-links graphs shown for cases (1,2) and (5,12) in Figure 2 consist simply of squares or concentric nests of squares and can be generalized to the following general rule for case (a,b).

To construct the missing-links graph for Chinese labyrinth (a,b), draw about each superlattice point a concentric nest of (a-1)/2 squares, the smallest of side 2, the largest of side (a-1) and about the centroid of each supertile a concentric nest of b/2 squares, the smallest of side 1, the largest of side (b-1).

Mitchell

However, if we try this rule out for any case where $\mathbf{b}=0$ or $\mathbf{a}$ and $\mathbf{b}$ share a common factor, $\mathbf{c}$ , then it fails to deliver a monohedral tessellation; we obtain instead a tessellation made up of polyominoes sitting in holes in larger polyominoes. A construction (there may well be others) for such cases involves thumbed squares; see Figure 2 for cases (9,6) and (7,0). I employ the shorthand <\mathbf{s}; \mathbf{l}, \mathbf{w}> , to describe a square of side $\mathbf{s}$ with thumbs of length $\mathbf{l}$ and width $\mathbf{w}$ . The rule for common-factor missing-links graphs is:

About each superlattice point construct a nest of polygons, each nest consisting of $(\mathbf{a}-\mathbf{c})/2$ thumbed squares, of thumb-length $(\mathbf{c}-1)/2$ , the smallest being < 2;(\mathbf{c} - \mathbf{1}) / 2,1> , the largest < (\mathbf{a} - \mathbf{c});(\mathbf{c} - \mathbf{1}) / 2,(\mathbf{a} - \mathbf{c} - \mathbf{1})> . The thumbs point clockwise. Between these nests we can precisely insert the following figures, namely:

About each supertile centroid construct a nest of polygons as follows.

1). if $c$ is of the form $4m+1$ ( $m=0,1,2\dots$ ) each nest consists of $(2b-c+1)/4$ squares, the smallest of side 1, the largest of side $(2b-c-1)/2$ , within $(c-1)/4$ thumbed squares of thumb-length $(c+1)/2$ , being <(2b - c + 3)/2; (c + 1)/2, 1> , <(2b - c + 7)/2; (c + 1)/2, 3> , …, <(b - 1); (c + 1)/2, (c - 3)/2> . The thumbs point anticlockwise.

or 2). if $c$ is of the form $4m+3$ ( $m=0,1,2\dots$ ) each nest consists of $(2b-c-1)/4$ squares, the smallest of side 1, the largest of side $(2b-c-3)/2$ , within $(c+1)/4$ thumbed squares of thumb-length $(c-1)/2$ , being: <(2b - c + 1)/2; (c - 1)/2, 1> , <(2b - c + 5)/2; (c - 1)/2, 3, \ldots , <(b - 1); (c - 1)/2, (c - 1)/2> . The thumbs point clockwise.

No Chinese labyrinth can be drawn for maverick case (3,0). An attempt leads to case (3,3) in Figure 3, in which each supertile has a dyad axis of symmetry at its centroid but the symmetry of the tessellation is still 442. The two sets of tetrad axes are now both situated at lattice points, with different environments. Either set could be chosen as superlattice points with separation “forced apart” to (3,3) and specifying a member of a new family of lattice labyrinths having both separation parameters odd. Table 2 lists lowest-order members of the serpentine lattice labyrinth family, named from the characteristic supertile shape.

Table 2: Lowest-order members of the serpentine lattice labyrinth family.

Figure 3 includes the lowest-order basic tessellation of the serpentine family, case (3,1). Each labyrinth is generated by a fundamental domain of area $\mathbf{D}$ , being a pair of identically shaped, diagonally symmetrical supertiles of area $\mathbf{S}$ , oriented at $90^{\circ }$ to each other, so that $\mathbf{D}={\mathbf{a}}^2+{\mathbf{b}}^2=2\mathbf{S}$ . Note that the sequence of value of $\mathbf{S}$ in Table 2 is the same as for Chinese labyrinths in Table 1, all being of the form $1+4\mathbf{m}$ . Other $1+2\mathbf{m}$ values seem to be allowed by the symmetry, but cannot be the sum of two squares [3]. The construction of missing-links graphs for serpentine lattice labyrinths is closely analogous to that for the Chinese family. In all cases where the separation parameters are co-prime, the standard missing-links graph consists of concentric nests of squares, the smallest of side 2, about each set of tetrad axes, but

Lattice Labyrinth Tessellations

in cases where $\mathbf{a}=\mathbf{b}$ or $\mathbf{a}$ and $\mathbf{b}$ share a common factor, we once again need to call on thumbed squares. I have found rules that can be applied to all allowable pairs of separation parameters, but other non-standard constructions are possible in at least some cases; some are included in my workbook [7].

Figure 3: Serpentine lattice labyrinth (25,15), family friends and the basic tessellation.

We have looked at lattice labyrinth families of tessellations for separation parameters $(\mathbf{a},\mathbf{b})$ of form (odd,even) and (odd,odd). Lattice labyrinths displaying 442 rotational symmetry also exist for (even,even) parameters. Description of their intriguing properties must await another occasion.

Lattice Labyrinth Tessellations Constructed on the Triangular Lattice

The techniques employed for constructing lattice labyrinths on the square lattice can be extended to generate even more astonishing tessellations on the triangular lattice. Figure 4 shows the tessellation of triangles and some members of the trefoil lattice labyrinth family which is its generalization. They are diverse in form; one having an illusory three-dimensional appearance. The lattice points, at each intersection of six links of the triangular lattice “graph paper”, are omitted from this crowded figure.

Mitchell

Figure 4: Some trefoil lattice labyrinths and the basic tessellation of equilateral triangles.

Figure 4 needs explaining. The rotational symmetry of the basic tessellation of equilateral triangles comprises hexads (a $60^{\circ }$ rotation leaves the pattern unchanged) at each lattice point, triads (a $120^{\circ }$ rotation leaves the pattern unchanged) at the centroid of each triangular tile and dyads at the center of each lattice link. The shorthand for the symmetry pattern is 632 [2]. All tessellations in Figure 4 share this symmetry. Note that, once again, every lattice point is connected by the tessellation graphs, so that the supertiles are slim polyiamonds, no more than one triangle wide and enclosing no lattice points. Each higher-order trefoil lattice labyrinth tessellation is monohedral and homeomorphic to the basic tessellation of triangles, having two sets of identically-shaped supertiles oriented at $180^{\circ }$ degrees to each other.

How do we set out a trefoil labyrinth on the triangular lattice? The array of superlattice points, at each of which is a hexad axis of symmetry, is another triangular lattice of superlattice points, larger and usually inclined to the original lattice. Figure 5 shows how superlattice points are set out at separation parameters $(\mathbf{e},\mathbf{f})$ , in this case (4,3), measured along axes at $60^{\circ }$ to each other.

Figure 5: How to set out superlattice points at separation $(\mathbf{e},\mathbf{f})$ on the triangular lattice.

Lattice Labyrinth Tessellations

The area of each large triangle measured in triangles of the original lattice equals ${\mathbf{e}}^2+\mathbf{ef}+{\mathbf{f}}^2$ (termed a Loeschian number), each supertile of a trefoil lattice labyrinth consisting of a central triangle and three identical arms, so of the form $1+3\mathbf{m}$ , implying the Diophantine equation ${\mathbf{e}}^2+\mathbf{ef}+{\mathbf{f}}^2=1+3\mathbf{m}$ . Once again, the Diophantine equation gives only a necessary condition for the existence of members of the trefoil lattice labyrinth family, but the missing-links algorithm comes to our rescue, in some cases at least, supplying sufficiency by enabling construction. On the triangular lattice, each lattice point is a vertex where six lattice links meet. Trefoil labyrinth superlattice points lie where six supertiles meet, so all lattice links to them are used in the tessellation graph but the graph uses only two of the links meeting at every other lattice point. The missing-links graph must therefore include four lattice links to every lattice point except for the superlattice points. This can be achieved by two Hamiltonian cycles intersecting at each lattice point. Simple and elegant cyclic graph elements can be used, including hexagons, hexagrams and other hexagonally symmetrical figures nested about the superlattice points and triangles and other trigonally symmetrical figures nested about the triad axes, as seen in Figure 4. Cycles nested about the dyad axes may also be needed. I have discovered general rules for some trefoil subfamilies, for instance with separation parameters of form $(\mathbf{e},1)$ . Figure 6, trefoil $(44,1)$ is dedicated to my eldest daughter, born in 1981, this being the number of triangles in each supertile. Such sub-families are infinitely numerous and I’ve yet to succeed in the addictive search for a fugitive general solution.

Figure 6: Six supertiles of birth-year trefoil lattice labyrinth (44,1), supertile area 1981 triangles.

The regular tessellation of hexagons can also be set out on the triangular lattice and, if we allow just the central lattice point in each supertile to remain unconnected by the tessellation graph, this honeycomb tessellation is also the basic tessellation of a family, the honeycomb lattice labyrinths, which again display 632 symmetry. Each supertile, being hexagonally symmetrical, must have an area divisible by 6, which implies the Diophantine equation $2({\mathbf{e}}^2+\mathbf{ef}+{\mathbf{f}}^2)=6\mathbf{m}$ , so that ${\mathbf{e}}^2+\mathbf{ef}+{\mathbf{f}}^2=3\mathbf{m}$ . It is rewarding that this equation specifies just those Loeschian numbers and separation parameter pairs not allowable for trefoil labyrinths. Figure 9.3 also shows examples of the dart and diamond lattice labyrinth families. These families both obey ${\mathbf{e}}^2+\mathbf{ef}+{\mathbf{f}}^2=3\mathbf{m}$ and elegantly partition all possible cases between them. Dart

Mitchell

labyrinths can only be drawn for (even, even) cases of (e,f), while diamond labyrinths can only be drawn for (odd, odd) and (odd, even) cases. Figure 7 also shows the basic tessellations of the dart and diamond families. Note how the fundamental domain of diamond labyrinths consists of three supertiles oriented at $120^{\circ }$ to each other, dart labyrinths having six supertiles at $60^{\circ }$ to each other. Missing-links graphs of these families are harder to discover and to generalize than are those of trefoil and honeycomb labyrinths. Honeycomb, dart and diamond missing-links graphs include non-cyclic elements, as seen in Figure 7.

Figure 7: Lattice labyrinth families for separation parameters obeying $e^2+ef+f^2=3m$ .

Apparently complex lattice labyrinth tessellations can be thought of as generalizations of simple basic tessellations. Tessellations of unlimited intricacy can be found using the missing-links algorithm. Constructing original examples and seeking general rules are challenging and rewarding pastimes.

References

[1] Bosch, Robert, Sarah Fries, Måneka Puligandla & Karen Ressler, From Path-Segment Tiles to Loops and Labyrinths, Proceedings of Bridges 2013, pp.119-126 [2] Conway, John H., Heidi Burgiel & Chaim Goodman-Strauss, The Symmetries of Things, Taylor & Francis, 2008. [3] Conway, John H. & Richard K. Guy The Book of Numbers, Copernicus, 1996, pp. 146,147. [4] Dye, Daniel Sheets, The New Book of Chinese Lattice Designs, Dover, 1981. [5] Fukuda, Hiroshi et al, Polyominoes and Polyiamonds as Fundamental Domains of Isohedral Tilings with Rotational Symmetry, Symmetry 2011, 3, pp.828-851 [6] Mitchell, D.J., Some Aspects of Demand-actuated Public Transport Systems, University of Birmingham (unpublished Ph.D. thesis), 1972, pp 187-209 & 332-344. [7] Mitchell, David, Lattice Labyrinth Tessellations bold art from modest mathematics, Tarquin 2013.