3.2k+

Tilings

Authored by: Doris Schattschneider , Marjorie Senechal

Discrete and Computational Geometry

Print publication date:  April  2004
Online publication date:  April  2004

Print ISBN: 9781584883012
eBook ISBN: 9781420035315

10.1201/9781420035315.ch3

Abstract

Tilings of surfaces and packings of space have been of interest to artisans and manufacturers throughout history; they are a means of artistic expression and lend economy and strength to modular constructions. Today scientists and mathematicians study tilings because they pose interesting mathematical questions and provide mathematical models for such diverse structures as the molecular anatomy of crystals, cell packings of viruses, n-dimensional algebraic codes, and “nearest neighbor” regions for a set of discrete points. The basic questions are: What bodies can tile space? In what ways do they tile? However, in this generality such questions are intractable. To study tiles and tilings, we must impose constraints.

Introduction

Tilings of surfaces and packings of space have been of interest to artisans and manufacturers throughout history; they are a means of artistic expression and lend economy and strength to modular constructions. Today scientists and mathematicians study tilings because they pose interesting mathematical questions and provide mathematical models for such diverse structures as the molecular anatomy of crystals, cell packings of viruses, n-dimensional algebraic codes, and “nearest neighbor” regions for a set of discrete points. The basic questions are: What bodies can tile space? In what ways do they tile? However, in this generality such questions are intractable. To study tiles and tilings, we must impose constraints.

Even with constraints the subject is unmanageably large. In this chapter we restrict ourselves, for the most part, to tilings of unbounded spaces. In the next section we present some general results that are fundamental to the subject as a whole. Section 3.2 addresses tilings with congruent tiles. In Section 3.3 we discuss the classical subject of periodic tilings, which continues to be enriched with new results. Next, we briefly describe the newer theory of nonperiodic and aperiodic tilings, both of which are discussed in more detail in Chapter 62. We conclude with a very brief description of some kinds of tilings not considered here.

3.1  General Considerations

In this section we define terms that will be used throughout the chapter and state some basic results. Taken together, these results state that although there is no algorithm for deciding which bodies are tiles, there are criteria for deciding the question in certain cases. We can obtain some quantitative information about the tiling in particularly well-behaved cases.

Unless otherwise stated, we assume that S is an n-dimensional space, either Euclidean $( E n )$

or hyperbolic. We also assume that the tiles are bounded and the tilings are locally finite (see the Glossary below). Throughout this chapter, n is the dimension of the space in which we are working.

Glossary

Body

:A bounded region (of S) that is the closure of its (nonempty) interior.

Tiling (of S)

:A decomposition of S into a countable number of n-dimensional bodies whose interiors are pairwise disjoint. In this context, the bodies are also called n-cells and are the tiles of the tiling (see below). Synonyms: tessellation , parquetry (when n = 2), honeycomb (for n ≥ 2).

Tile

:A body that is an n-cell of one or more tilings of S. To say that a body tiles a region RS means that R can be covered exactly by copies of the body without gaps or overlaps.

Locally finite tiling

:Every n-ball of finite radius in S meets only finitely many tiles of the tiling.

Prototile set (for a tiling $T$ of S)

:A minimal subset of tiles in $T$

such that each tile in the tiling $T$ is the congruent image of one of those in the prototile set. The tiles in the set are called prototiles and the prototile set is said to admit $T$ .

k-face (of a tiling)

:An intersection of at least nk + 1 tiles of the tiling that is not contained in a j-face for j < k. (The 0-faces are the vertices and 1-faces the edges ; the (n−1)-faces are simply called the faces of the tiling.)

Patch (in a tiling)

:A set of tiles whose union is homeomorphic to an n-ball. See Figure 3.1.1. A spherical patch P(r, s) is the set of tiles whose intersection with the ball of radius r centered at s is nonempty, together with any additional tiles needed to complete the patch (that is, to make it homeomorphic to an n-ball).

Figure 3.1.1   Three patches in a tiling of the plane by squares.

Normal tiling

:A tiling in which (i) each prototile is homeomorphic to an n-ball, and (ii) the prototiles are uniformly bounded (there exist r > 0 and R > 0 such that each prototile contains a ball of radius r and is contained in a ball of radius R). It is technically convenient to include a third condition: (iii) the intersection of every pair of tiles is a connected set. (A normal tiling is necessarily locally finite.)

Face-to-face tiling (by polytopes)

:A tiling in which the faces of the tiling are also the (n−1)-dimensional faces of the polytopes. (A face-to-face tiling by convex polytopes is also k-face-to-k-face for 0 ≤ kn − 1.) In dimension 2, this is an edge-to-edge tiling by polygons, and in dimension 3, a face-to-face tiling by polyhedra.

Dual tiling

:Two tilings

are dual if there is an incidence-reversing bijection between the k-faces of $T$ and the (nk)-faces of $T *$ (see Figure 3.1.2).

Voronoi (Dirichlet) tiling

:A tiling whose tiles are the Voronoi cells of a discrete set Λ of points in S. The Voronoi cell of a point p ∊ Λ is the set of all points in S that are at least as close to p as to any other point in Λ (see Chapter 23).

Delaunay (or Delone) tiling

:A face-to-face tiling by convex circumscribable polytopes (i.e., the vertices of each polytope lie on a sphere).

Figure 3.1.2   A Voronoi tiling (solid lines) and its Delaunay dual (dashed lines).

Isometry

:A distance-preserving self-map of S.

Symmetry group (of a tiling)

:The set of isometries of S that map the tiling to itself.

Main Results

1. The Undecidability Theorem. There is no algorithm for deciding whether or not an arbitrary body or set of bodies admits a tiling of S [Ber66].
2. The Extension Theorem (for $E n$ ). Let A be any finite set of bodies, each homeomorphic to a closed n-ball. If A tiles regions that contain arbitrarily large n-balls, then A admits a tiling of $E n$ . (These regions need not be nested, nor need any of the tilings of the regions be extendable!) The proof for n = 2 in [GS87] extends to En with minor changes.
3. The Normality Lemma (for $E n$ ). In a normal tiling, the ratio of the number of tiles that meet the boundary of a spherical patch to the number of tiles in the patch tends to zero as the radius of the patch tends to infinity. In fact, a stronger statement can be made: For sS let t(r, s) be the number of tiles in the spherical patch P(r, s). Then, in a normal tiling, for every x > 0,
$lim r → ∞ t ( r + x , s ) − t ( r , s ) t ( r , s ) = 0.$
The proof for n = 2 in [GS87] extends to $E n$ with minor changes.
4. Euler’s Theorem for tilings of $E 2$ . Let $T$ be a normal tiling of $E 2$ , and let t(r, s), e(r, s), and v(r, s) be the numbers of tiles, edges, and vertices, respectively, in the circular patch P(r, s). Then if one of the limits exists, so does the other, and $υ ( T ) − e ( T ) + 1 = 0$ . Like Euler’s Theorem for Planar Maps, on which the proof of this theorem is based, this result can be extended in various ways [GS87].
5. Voronoi Dual. Every Voronoi tiling has a Delaunay dual and conversely (see Figure 3.1.2) [Vor09].

3.2  Tilings by One Tile

To say that a body tiles $E n$

usually means that there is a tiling all of whose tiles are copies of this body. The artist M.C. Escher has demonstrated how intricate such tiles can be even when n = 2. But in higher dimensions the simplest tiles—for example, cubes—can produce surprises, as the recent counterexample to Keller’s conjecture attests (see below).

Glossary

Monohedral tiling

:A tiling with a single prototile.

r-morphic tile

:A prototile that admits exactly r distinct monohedral tilings. Figure 3.2.1 shows a 5-morphic tile and all its tilings, and Figure 3.2.3 shows a 1-morphic tile and its tiling.

Figure 3.2.1   A pentamorphic tile.

k-rep tile

:A body for which k copies can be assembled into a larger, similar body. (Or, equivalently, a body that can be partitioned into k congruent bodies, each similar to the original.) More formally, a k-rep tile is a closed set A 1 in S with nonempty interior such that there are sets A 2, …, Ak congruent to A 1 that satisfy

for all ij and A 1 ∪ … ∪ Ak = g(A 1), where g is a similarity mapping. (Figure 3.2.2 shows a 3-dimensional chair rep tile and the second-level chair. An n-dimensional chair rep tile can be formed in a similar manner.)

Transitive action

:A group G is said to act transitively on a set {A 1,A 2, …} if the set is an orbit for G. (That is, for every pair Ai , Aj of elements of the set, there is a gij G such that gijAi = Aj .)

Regular system of points

:A discrete set of points on which an infinite group of isometries acts transitively.

Isohedral (tiling)

:A tiling whose symmetry group acts transitively on its tiles.

Anisohedral tile

:A prototile that admits monohedral tilings but no isohedral tilings. In Figure 3.2.3, the prototile admits a unique nonisohedral tiling; the shaded tiles are each surrounded differently, from which it follows that no isometry can map one to the other (and the tiling to itself). This tiling is periodic, however (see Section 3.3).

Figure 3.2.2   A 3-dimensional chair rep tile and a second-level chair in which seven copies surround the first.

Figure 3.2.3   An anisohedral tile (due to R. Penrose) and its unique tiling in which tiles are surrounded in two different ways.

Corona (of a tile P in a tiling $T$ )

:Define C 0(P) = P. Then Ck (P), the kth corona of P, is the set of all tiles QT for which there exists a path of tiles P = P 0, P 1, …, Pm = Q with mk in which $P i ∩ P i + 1 ≠ 0$

, i = 0, 1, …, m − 1.

Lattice

:The group of integral linear combinations of n linearly independent vectors in S. A point orbit of a lattice, often called a point lattice , is a particular case of a regular system of points.

Translation tiling

:A monohedral tiling of S in which every tile is a translate of a fixed prototile. See Figure 3.2.4.

Lattice tiling

:A monohedral tiling on whose tiles a lattice of translation vectors acts transitively. Figure 3.2.4 is not a lattice tiling since it is invariant by multiples of just one vector.

n-parallelotope

:A convex n-polytope that tiles $E n$

by translation.

Figure 3.2.4   A translation non-lattice tiling.

Belt (of an n-parallelotope)

:A maximal subset of parallel (n−2)-faces of a parallelotope in $E n$

. The number of (n−2)-faces in a belt is its length.

Center of symmetry (for a set A in $E n$ )

:A point aA such that A is invariant under the mapping x → 2ax; the mapping is called central inversion and an object that has a center of symmetry is said to be centrosymmetric .

Stereohedron

:A convex polytope that is the prototile of an isohedral tiling. A Voronoi cell of a regular system of points is a stereohedron.

Linear expansive map

:A linear transformation all of whose eigenvalues have modulus greater than one.

Main Results

1. The Local Theorem. Let $T$ be a monohedral tiling of S, and for $P ∈ T$ , let Si (P) be the subgroup of the symmetry group of P that leaves invariant Ci (P), the i th corona of P. $T$ is isohedral if and only if there exists an integer k > 0 for which the following two conditions hold: (a) for all $P ∈ T$ , S k−1(P) = Sk (P) and (b) For every pair of tiles P, P′ in $T$ , there exists an isometry γ such that γ(P) = P′ and γ(Ck (P)) = Ck (P′). In particular, if P is asymmetric, then $T$ is isohedral if and only if condition (b) holds for k = 1 [DS98].
2. A convex polytope is a parallelotope if and only if it is centrosymmetric, its faces are centrosymmetric, and its belts have lengths four or six. First proved by Venkov, this theorem was rediscovered independently by McMullen [Ven54, McM80].
3. The number |F| of faces of a convex parallelotope in $E n$ satisfies Minkowski’s inequality, 2n ≤ |F| ≤ 2(2 n − 1). Both upper and lower bounds are realized in every dimension [Min97].
4. The number of faces of an n-dimensional stereohedron in $E n$ is bounded. In fact, if a is the number of translation classes of the stereohedron in an isohedral tiling, then the number of faces is at most the Delaunay bound 2 n (1+a) − 2 [Del61].
5. Using a classification system that takes into account the symmetry groups of the tilings and their tiles, the combinatorial structure of the tiling, and the ways in which the tiles are related to adjacent tiles, Grünbaum and Shephard proved that there are 81 classes of isohedral tilings of $E 2$ , 93 classes if the tiles are marked (that is, they have decorative markings to express symmetry in addition to the tile shape) [GS77]. There is an infinite number of classes of isohedral tilings of $E n$ , n > 2.
6. Anisohedral tiles exist in $E n$ for every n ≥ 2 [GS80]. (The first example, given for n = 3 by Reinhardt [Rei28], was the solution to part of Hilbert’s 18th problem.) H. Heesch gave the first example for n = 2 [Hee35] and R. Kershner the first convex examples [Ker68].
7. Every n-parallelotope admits a lattice tiling. However, for n ≥ 3, there are nonconvex tiles that tile by translation but do not admit lattice tilings [SS94].
8. A lattice tiling of $E n$ by unit cubes must have a pair of cubes sharing a whole face [Min07, Haj42]. However, a famous conjecture of Keller, which stated that for every n, any tiling of $E n$ by congruent cubesmust contain at least one pair of cubes sharing a whole face, is false: for n ≥ 10, there are translation tilings by unit cubes in which no two cubes share a whole face [LS92].
9. Every linear expansive map that transforms the lattice $ℤ n$ of integer vectors into itself defines a family of k-rep tiles; these tiles, which usually have fractal boundaries, admit lattice tilings [Ban91].

Open Problems

1. Which convex n-polytopes in $E n$ are prototiles for monohedral tilings of $E n$ ? This is unsolved for all n ≥ 2 (see [GS87] for the case n = 2; the list of convex pentagons that tile has not been proved complete). For higher dimensions, little is known; it is not even known which tetrahedra tile $E 3$ [GS80, Sen81].
2. Heesch’s Problem. Is there an integer kn , depending only on the dimension n of the space S, such that if a body A can be completely surrounded kn times by tiles congruent to A, then A is a prototile for a monohedral tiling of S? (A is completely surrounded once if A, together with congruent copies that have nonempty intersection with A, tile a patch containing A in its interior.) When $S = E 2$ , k 2 > 5. The body shown in Figure 3.2.5 can be completely surrounded three times but not four; William Rex Marshall and, independently, Casey Mann, found 4-corona tiles, and Mann 5-corona tiles [Man01]. This problem is unsolved for all n.
3. Keller’s conjecture is true for n ≤ 6 and false for n ≥ 10 (see Result 8 above). The cases n = 7, 8, and 9 are still open.
4. Do r-morphic tiles exist for every positive integer r? Fontaine and Martin have shown the answer is yes in $E 2$ for r ≤ 10 [FM84].
5. Find a good upper bound for the number of faces of an n-dimensional stereohedron. Delaunay’s bound, stated above, is evidently much too high; for example, it gives 390 as the bound in $E 3$ , while the maximal known number of faces of a three-dimensional stereohedron (found by P. Engel [Eng81]) is 38.
6. For monohedral (face-to-face) tilings by convex polytopes there is an integer kn , depending only on the dimension n of S, that is an upper bound for the constant k in the Local Theorem [DS98]. Find the value of this kn . For the Euclidean plane $E 2$ it is known that k 2 = 1 (convexity of the tiles is not necessary) [SD98], but for the hyperbolic plane, k 2 ≥ 2 [Mak92]. For $E 3$ , it is known that 2 ≤ k 3 ≤ 5.

Figure 3.2.5   Ammann’s 3-corona tile cannot be surrounded by a fourth corona. 4-corona and 5-corona tiles also exist.

3.3  Periodic Tilings

Periodic tilings have been studied intensely, in part because their applications range from ornamental design to crystallography, and in part because many techniques (algebraic, geometric, and combinatorial) are available for studying them.

Glossary

Periodic tiling of $E n$

:A tiling, not necessarily monohedral, whose symmetry group contains an n-dimensional lattice. This definition can be adapted to include “subperiodic” tilings (those whose symmetry groups contain 1 ≤ k < n linearly independent vectors) and tilings of other spaces (for example, cylinders). Tilings in Figures 3.2.1, 3.2.3, 3.3.1, and 3.3.3 are periodic.

Fundamental domain (generating region) for a periodic tiling

:A minimal subset of S whose orbit under the symmetry group of the tiling is the whole tiling. A fundamental domain may be a tile (Figure 3.2.1), a subset of a single tile (Figure 3.3.1), or a subset of tiles (two shaded tiles in Figure 3.2.3).

Orbifold (of a tiling of S)

:The manifold obtained by identifying points of S that are in the same orbit under the action of the symmetry group of the tiling.

Free tiling

:A tiling whose symmetry group acts freely and transitively on the tiles.

k-isohedral (tiling)

:A tiling whose tiles belong to k transitivity classes under the action of its symmetry group. Isohedral means 1-isohedral (Figures 3.2.1, 3.3.1, and 3.3.3). The tiling in Figure 3.2.3 is 2-isohedral.

Equitransitive (tiling by polytopes)

:A tiling in which each combinatorial class of tiles forms a single transitivity class under the action of the symmetry group of the tiling.

k-isogonal (tiling)

:A tiling whose vertices belong to k transitivity classes under the action of its symmetry group. Isogonal means 1-isogonal.

k-uniform (tiling of a 2-dimensional surface)

:A k-isogonal tiling by regular polygons.

Uniform (tiling for n > 2)

:An isogonal tiling with congruent edges and uniform faces.

Flag of a tiling (of S)

:An ordered (n+1)-tuple (X 0, X 1, …, Xn ), with Xn a tile and Xk a k-face for 0 ≤ kn − 1, in which X i−1Xi for i = 1, …, n.

Regular tiling (of S)

:A tiling $T$

whose symmetry group is transitive on the flags of $T$ . (For n > 2, these are also called regular honeycombs.) See Figure 3.3.3.

k-colored tiling

:A tiling in which each tile has a single color, and k different colors are used. Unlike the case of map colorings, in a colored tiling adjacent tiles may have the same color.

Perfectly k-colored tiling

:A k-colored tiling for which each element of the symmetry group G of the uncolored tiling effects a permutation of the colors. The ordered pair (G, Π), where Π is the corresponding permutation group, is called a k-color symmetry group.

Classification of Periodic Tilings

The mathematical study of tilings (like most mathematical investigations) has been accompanied by the development and use of a variety of notations for classification of different “types” of tilings and tiles. Far from being merely names by which to distinguish types, these notations tell us the investigators’ point of view and the questions they ask. Notation may tell us the global symmetries of the tiling, or how each tile is surrounded, or the topology of its orbifold. Notation makes possible the computer implementation of investigations of combinatorial questions about tilings.

Periodic tilings are classified by symmetry groups and, sometimes, by their skeletons (of vertices, edges, …, (n−1)-faces). The groups are known as crystallographic groups; up to isomorphism, there are 17 in $E 2$

and 219 in $E 3$ . For $E 2$ and $E 3$ , the most common notation for the groups has been that of the International Union of Crystallography (IUCr) [Hah83]. This is cross-referenced to earlier notations in [Sch78]. Recently developed notations include Delaney-Dress symbols [Dre87] and orbifold notation for n = 2 [Con92, CH02] and for n = 3 [CDHT01].

Glossary

International symbol (for periodic tilings of )

:Encodes lattice type and particular symmetries of the tiling. In Figure 3.3.1, the lattice unit diagram at the right encodes the symmetries of the tiling and the IUCr symbol p31m indicates that the highest-order rotation symmetry in the tiling is 3-fold, that there is no mirror normal to the edge of the lattice unit, and that there is a mirror at 60° to the edge of the lattice unit. These symbols are augmented to denote symmetry groups of perfectly 2-colored tilings.

Delaney-Dress symbol (for tilings of Euclidean, hyperbolic, or spherical space of any dimension)

:Associates an edge-colored and vertex-labeled graph derived from a chamber system (a formal barycentric subdivision) of the tiling. In Figure 3.3.2, the nodes of the graph represent distinct triangles A, B, C, D in the chamber system, and colored edges (dashed, thick, or thin) indicate their adjacency relations. Numbers on the nodes of the graph show the degree of the tile that contains that triangle and the degree of the vertex of the tiling that is also a vertex of that triangle.

Figure 3.3.1   An isohedral tiling with standard IUCr lattice unit shaded; a half-leaf is a fundamental domain. The classification symbols are for the symmetry group of the tiling.

Figure 3.3.2   A chamber system of the tiling in Figure 3.3.1 determines the graph that is its Delaney-Dress symbol.

Orbifold notation (for symmetry groups of tilings of 2-dimensional surfaces of constant curvature)

:Encodes properties of the orbifold induced by the symmetry group of a periodic tiling of the Euclidean plane or hyperbolic plane, or a finite tiling of the surface of a sphere; introduced by Conway. In Figure 3.3.1, the first 3 in the orbifold symbol 3*3 for the symmetry group of the tiling indicates there is a 3-fold rotation center (gyration point) that becomes a cone point in the orbifold, while *3 indicates that the boundary of the orbifold is a mirror with a corner where three mirrors intersect.

See Table 3.3.1 for the IUCr and orbifold notations for $E 2$

.

Table 3.3.1   IUCr and orbifold notations for the 17 symmetry groups of periodic tilings of E 2 .

IUCr

ORBIFOLD

IUCr

ORBIFOLD

p1

o or o1

p3

333

pg

×× or 1××

p31m

3*3

cm

*× or 1*×

p3m1

*333

pm

** or 1**

p4

442

p2

2222

p4g

4*2

pgg

22×

p4m

*442

pmg

22*

p6

632

cmm

2*22

p6m

*632

pmm

*2222

Isohedral tilings of $E 2$

fall into 11 combinatorial classes, typified by the Laves nets (Figure 3.3.3). The Laves net for the tiling in Figure 3.3.1 is [3.6.3.6]; this gives the vertex degree sequence for each tile. In an isohedral tiling, every tile is surrounded in the same way. Grünbaum and Shephard provide an incidence symbol for each isohedral type by labeling and orienting the edges of each tile [GS79]. Figure 3.3.4 gives the incidence symbol for the tiling in Figure 3.3.1. The tile symbol a + a b + b records the cycle of edges of a tile and their orientations with respect to the (arrowed) first edge (+ indicates the same, − indicates opposite orientation). The adjacency symbol b a records for each different letter edge of a single tile, beginning with the first, the edge it abuts in the adjacent tile and their relative orientations (now − indicates same, + opposite). These symbols can be augmented to adjacency symbols to denote k-color symmetry groups. Earlier, Heesch devised signatures for the 28 types of tiles that could be fundamental domains of isohedral tilings without reflection symmetry [HK63]; this signature system was extended in [BW94].

Figure 3.3.3   The 11 Laves nets. The three regular tilings of E 2 are at the top of the illustration.

Figure 3.3.4   Labeling and orienting the edges of the isohedral tiling in Figure 3.3.1 determines its Grünbaum-Shephard incidence symbol.

Main Results

1. If a finite prototile set of polygons admits an edge-to-edge tiling of the plane that has translational symmetry, then the prototile set also admits a periodic tiling [GS87].
2. The number of symmetry groups of periodic tilings in $E n$ is finite (this is a famous theorem of Bieberbach [Bie10] that partially solved Hilbert’s 18th problem: see also Chapter 62); the number of symmetry groups of corresponding tilings in hyperbolic n-space, for n = 2 and n = 3, is infinite.
3. Every k-isohedral tiling of the Euclidean plane, hyperbolic plane, or sphere can be obtained from a (k−1)-isohedral tiling by a process of splitting (splitting an asymmetric prototile) and gluing (amalgamating two or more equivalent asymmetric tiles adjacent in the tiling into one new tile) [Hus93]; there are 1270 classes of normal 2-isohedral tilings and 48,231 classes of normal 3-isohedral tilings of $E 2$ .
4. Classifying isogonal tilings in a manner analogous to isohedral ones, Grünbaum and Shephard have shown [GS78a] that there are 91 classes of normal isogonal tilings of $E 2$ (93 classes if the tiles are marked). Similarly [GS78b], there are 26 classes of normal tilings of $E 2$ for which the symmetry group acts transitively on the edges (30 if the tiles are marked); these tilings are called isotoxal . See also [GS87].
5. There are 88 combinatorial classes of periodic tilings of $E 3$ for which the symmetry group acts transitively on the faces of the tiling [DHM93].
6. For every k, the number of k-uniform tilings of $E 2$ is finite. There are 11 uniform tilings of $E 2$ (also called Archimedean , or semiregular ), of which 3 are regular. The Laves nets in Figure 3.3.3 are duals of these 11 uniform tilings [GS87, Sections 2.1, 2.2]. There are 28 uniform tilings of $E 3$ [Grü94] and 20 2-uniform tilings of $E 2$ [Krö69]; see also [GS87, Section 2.2]. In the hyperbolic plane, uniform tilings with vertex valence 3 and 4 have been classified [GS79].
7. In any equitransitive tiling of $E 2$ by convex polygons, the maximum number of edges of any tile is 66 [DGS87].
8. There are finitely many regular tilings of $E n$ (three for n = 2, one for n = 3, three for n = 4, and one for each n > 4) [Cox63]. There are infinitely many normal regular tilings of the hyperbolic plane, four of hyperbolic 3-space, five of hyperbolic 4-space, and none of hyperbolic n-space if n > 4 [Sch83, Cox54].
9. If two orbifold symbols for a tiling of the Euclidean or hyperbolic plane look exactly the same except for the numerical values of their digits, which may differ by a permutation of the natural numbers (such as *632 and *532), then the number of k-isohedral tilings for each of these orbifold types is the same [BH96].
10. There is a one-to-one correspondence between perfect k-colorings of a free tiling and the subgroups of index k of its symmetry group. See [Sen79].

Open Problems

1. Does every convex pentagon that tiles $E 2$ admit a k-isohedral tiling for some k ≥ 1, and if so, is there an upper bound on k? (All pentagons known to tile the plane admit k-isohedral tilings, with k ≤ 3.)
2. Classify uniform tilings of the hyperbolic plane for the cases of vertex valences greater than 4.
3. Enumerate the uniform tilings of $E n$ for n > 3. (Some uniform tilings for $E n$ , n > 3, are discussed in [Joh04].)
4. Delaney-Dress symbols and orbifold notations have made progress possible on the classification of k-isohedral tilings in all three 2-dimensional spaces of constant curvature; extend this work to higher-dimensional spaces.

3.4  Nonperiodic and Aperiodic Tilings

Nonperiodic tilings are found everywhere in nature, from cracked glazes to biological tissues to real crystals. In a remarkable number of cases, such tilings exhibit strong regularities. For example, many such tilings have simplicial duals. Others repeat on increasingly larger scales. An even larger class of tilings are those now called repetitive, in which every bounded configuration appearing anywhere in the tiling is repeated infinitely many times throughout it (see below). Aperiodic tilings—those whose prototile sets admit only nonperiodic tilings—are particularly interesting. They were first introduced to prove the Undecidability Theorem (Section 3.1). Later, after Penrose found pairs of aperiodic prototiles (see Figure 3.4.1), they became popular in recreational mathematical circles. Their deep mathematical properties were first studied by Penrose, Conway, de Bruijn, and others. After the discovery of “quasicrystals” in 1984, aperiodic tilings became the focus of intense research. The basic ideas of this rapidly developing subject are only introduced here; they are discussed in more detail in Chapter 62.

Figure 3.4.1   Portions of Penrose tilings of the plane (a) by rhombs; (b) by kites and darts. The matching rules that force nonperiodicity are not shown (see Chapter 62).

Glossary

Nonperiodic tiling

:A tiling with no translation symmetry.

Hierarchical tiling

:A tiling whose tiles can be composed into larger tiles, called level-one tiles, whose level-one tiles can be composed into level-two tiles, and so on ad infinitum. In some cases it is necessary to partition the original tiles before composition.

Self-similar tiling

:A hierarchical tiling for which the larger tiles are copies of the prototiles (all enlarged by a constant expansion factor λ). k-rep tiles are the special case when there is just one prototile (Figure 3.2.2).

Uniquely hierarchical tiling

:A tiling whose j-level tiles can be composed into (j+1)-level tiles in only one way (j = 0, 1, …).

Composition rule (for a hierarchical tiling)

:The equations T′i = m i1 T 1 ∪ … ∪ mikTk , i = 1, …, k, that describe the numbers mij of each prototile Tj in the next higher level prototile T′i . These equations define a linear map whose matrix has i, j entry mij .

Relatively dense configuration

:A configuration C of tiles in a tiling for which there exists a radius rC such that every ball of radius rC in the tiling contains a copy of C.

Repetitive

:A tiling in which every bounded configuration of tiles is relatively dense in the tiling.

Local isomorphism class

:A family of tilings such that every bounded configuration of tiles that appears in any of them appears in all of the others. (For example, the uncountably many Penrose tilings with the same prototile set form a single local isomorphism class.)

Projected tiling

:A tiling obtained by the canonical projection method (see Chapter 62).

Aperiodic prototile set

:A prototile set that admits only nonperiodic tilings; see Figure 3.4.1.

Aperiodic tiling

:A tiling with an aperiodic prototile set.

Matching rules

:A list of rules for fitting together the prototiles of a given prototile set.

Mutually locally derivable tilings

:Two tilings are mutually locally derivable if the tiles in either tiling can, through a process of decomposition into smaller tiles, or regrouping with adjacent tiles, or a combination of both processes, form the tiles of the other (see Figure 3.4.2).

Complex Perron number

:An algebraic integer that is strictly larger in modulus than its Galois conjugates (except for its complex conjugate).

Figure 3.4.2   The Penrose tilings by kites and darts and by rhombs are mutually locally derivable.

Main Results

1. Self-similar and projected tilings are repetitive (see [Sen95]).
2. Uniquely hierarchical tilings are nonperiodic (the proof given in [GS87] for n = 2 extends immediately to all n). Conversely, nonperiodic self-similar tilings have the unique composition property [Sol98].
3. For each complex Perron number λ there is a self-similar tiling with expansion λ [Ken95].
4. “Irrational” projected tilings are nonperiodic (see Chapter 62).
5. The prototile sets of certain irrational projected tilings can be equipped with matching rules so that all tilings admitted by the prototile set belong to a single local isomorphism class (see Chapter 62).
6. Mutual local derivability is an equivalence relation on the set of all tilings. The existence or nonexistence of hierarchical structure and matching rules is a class property [KSB93].
7. Certain convex biprisms admit only nonperiodic monohedral tilings of $E 3$ if no mirror-image copies of the tiles are allowed [Sch88]; see Figure 3.4.3. These tiles can be altered to produce nonconvex aperiodic prototiles for $E 3$ [Dan95].
8. The prototile set of every uniquely hierarchical tiling can be equipped with matching rules that force the hierarchical structure [Goo98].

Figure 3.4.3   Conway’s biprism consists of two prisms fused at a common rhombus face. Small angle of rhombus is acos(3/4) ≈ 41.4°; diagonal of prism ≈ 2.87. When assembled, the vertices of the rhombus that is a common face of the two prisms are the poles of two 2-fold rotation axes.

Open Problems

Does there exist a prototile in $E 2$

that is aperiodic? Does there exist a convex prototile for $E 3$ that is aperiodic without restriction?

3.5  Other Tilings

There is a vast literature on tilings (or dissections) of bounded regions (such as rectangles and boxes, polygons, and polytopes) by tiles to satisfy particular conditions. This and much of the recreational literature focuses on tilings by tiles of a particular type, such as tilings by rectangles, tilings by clusters of n-cubes (polyominoes—see Chapter 15–and polycubes) or n-simplices (polyiamonds in $E 2$

), or tilings by recognizable animate figures. In the search for new ways to produce tiles and tilings, both mathematicians (such as P.A. MacMahon [Mac21]) and amateurs (such as M.C. Escher [Sch90]) have contributed to the subject. Recently the search for new shapes that tile a given bounded region S has produced knotted tiles, toroidal tiles, and twisted tiles. Kuperberg and Adams have shown that for any given knot K, there is a monohedral tiling of $E 3$ (or of hyperbolic 3-space, or of spherical 3-space) whose prototile is a solid torus that is knotted as K. Also, Adams has shown that, given any polyhedral submanifold M with one boundary component in $E n$ , a monohedral tiling of $E n$ can be constructed whose prototile has the same topological type as M [Ada95].

Other directions of research seek to broaden the definition of prototile set: in new contexts, the tiles in a tiling may be homothetic (rather than congruent) images of tiles in a prototile set, or be topological images of tiles in a prototile set. For example, a tiling of $E n$

by polytopes in which every tile is combinatorially isomorphic to a fixed convex n-polytope (the combinatorial prototile) is said to be monotypic . It has been shown that in $E 2$ , there exist monotypic face-to-face tilings by convex n-gons for all n ≥ 3; in $E 3$ , every convex 3-polytope is the combinatorial prototile of a monotypic tiling [Sch84a]. Many (but not all) classes of convex 3-polytopes admit monotypic face-to-face tilings [DGS83, Sch84b].

Surveys

The following surveys are useful, in addition to the references below.

• [GS87]: The definitive, comprehensive treatise on tilings of $E 2$ , state of the art as of the mid-1980s. All subsequent work (in any dimension) has taken this as its starting point for terminology, notation, and basic results. The Main Results of our Section 3.1 can be found here.
• [Joh04]: A comprehensive and detailed account of uniform polytopes and honeycombs in Euclidean and non-Euclidean spaces of n dimensions.
• [Moo97]: The proceedings of the NATO Advanced Study Institute on the Mathematics of Aperiodic Order, held in Waterloo, Canada in August 1995.
• [Sch93]: A contemporary survey of tiling theory, especially useful for its accounts of monotypic and other kinds of tilings more general than those discussed in this chapter.
• [Sch02]: A recent brief survey of tiling.
• [Sen95]: Chapters 5 – 8 form an introduction to the emerging theory of aperiodic tilings.
• [SS94]: This book is especially useful for its account of tilings in $E n$ by clusters of cubes.

References

C. Adams . Tilings of space by knotted tiles. Math. Intelligencer, 17:41–51, 1995.
L. Balke and D.H. Huson . Two-dimensional groups, orbifolds and tilings. Geom. Dedicata, 60:89–106, 1996.
C. Bandt . Self-similar sets 5. Integer matrices and fractal tilings of Rn . Proc. Amer. Math. Soc., 112:549–562, 1991.
R. Berger . The undecidability of the domino problem. Mem. Amer. Math. Soc., 66:1–72, 1966.
L. Bieberbach . Über die Bewegungsgruppen der euklidischen Räume. (Erste Abh.). Math. Ann., 70:297–336, 1910.
H.-G. Bigalke and H. Wippermann . Reguläre Parkettierungen. B.I. Wissenschaftsverlag, Mannheim, 1994.
J.H. Conway . The orbifold notation for surface groups. In M. Liebeck and J. Saxl , editors, Groups, Combinatorics and Geometry, Cambridge University Press, 1992, pages 438–447.
J.H. Conway , O. Delgado Friedrichs , D.H. Huson , and W.P. Thurston . Three-dimensional orbifolds and space groups. Beiträge Algebra Geom., 42:475–507, 2001.
J.H. Conway and D.H. Huson . The orbifold notation for two-dimensional groups. Structural Chemistry, 13:247–257, 2002.
H.S.M. Coxeter . Regular honeycombs in hyperbolic space. In Proc. Internat. Congress Math., volume III, Nordhoff, Groningen and North-Holland, Amsterdam, 1954, pages 155–169. Reprinted in Twelve Geometric Essays, S. Illinois Univ. Press, Carbondale, 1968, and The Beauty of Geometry: Twelve Essays, Dover, Mineola, 1999.
H.S.M. Coxeter . Regular Polytopes, second edition. Macmillan, New York, 1963. Reprinted by Dover, New York, 1973.
L. Danzer . A family of 3D-spacefillers not permitting any periodic or quasiperiodic tilings. In G. Chapuis , editor, Proc. Aperiodic ’94. World Scientific, Singapore, 1995, pages 11–17.
L. Danzer , B. Grünbaum , and G.C. Shephard . Does every type of polyhedron tile three-space? Structural Topology, 8:3–14, 1983.
L. Danzer , B. Grünbaum , and G.C. Shephard . Equitransitive tilings, or how to discover new mathematics. Math. Mag., 60:67–89, 1987.
B.N. Delone . Proof of the fundamental theorem in the theory of stereohedra. Dokl. Akad. Nauk SSSR, 138:1270–1272, 1961. English translation in Soviet Math., 2:812–815, 1961.
N. Dolbilin and D. Schattschneider . The local theorem for tilings. In J. Patera , editor, Quasicrystals and Discrete Geometry, Fields Inst. Monogr. 10, Amer. Math. Soc., Providence, 1998, pages 193–199.
A.W.M. Dress . Presentations of discrete groups, acting on simply connected manifolds. Adv. Math., 63:196–212, 1987.
A.W.M. Dress , D.H. Huson , and E. Molnár . The classification of face-transitive 3-D tilings. Acta Cryst. Sect. A, 49:806–817, 1993.
P. Engel . Über Wirkungsbereichsteilungen von kubischer Symmetrie, Z. Kristallogr., 154:199–215, 1981.
A. Fontaine and G. Martin . Polymorphic polyominoes. Math. Mag., 57:275–283, 1984.
C. Goodman-Strauss . Matching rules and substitution tilings. Ann. of Math., 147:181–223, 1998.
B. Grünbaum . Uniform tilings of 3-space. Geombinatorics, 4:49–56, 1994.
B. Grünbaum and G.C. Shephard . The eighty-one types of isohedral tilings in the plane. Math. Proc. Cambridge Phil. Soc., 82:177–196, 1977.
B. Grünbaum and G.C. Shephard . The ninety-one types of isogonal tilings in the plane. Trans. Amer. Math. Soc., 242:335–353, 1978 and 249:446, 1979.
B. Grünbaum and G.C. Shephard . Isotoxal tilings. Pacific J. Math., 76:407–430, 1978.
B. Grünbaum and G.C. Shephard . Incidence symbols and their applications. In D.K. Ray-Chaudhuri , editor, Relations between Combinatorics and Other Parts of Mathematics, volume 34 of Proc. Sympos. Pure Math., Amer. Math. Soc., Providence, 1979, pages 199–244.
B. Grünbaum and G.C. Shephard . Tilings with congruent tiles. Bull. Amer. Math. Soc., 3:951–973, 1980.
B. Grünbaum and G.C. Shephard . Tilings and Patterns. Freeman, New York, 1987.
T. Hahn , editor. International Tables for Crystallography, volume A. Space Group Symmetry. Reidel, Dordrecht, 1983.
G. Hajos . Über einfache und mehrfache Bedeckung des n-dimensionalen Raumes mit einem Würfelgitter. Math Z., 47:427–467, 1942.
H. Heesch . Aufbau der Ebene aus kongruenten Bereichen. Nachr. Ges. Wiss. Göttingen, New Ser., 1:115–117, 1935.
H. Heesch and O. Kienzle . Flächenschluss. System der Formen lückenlos aneinanderschliessender Flachteile. Springer-Verlag, Berlin, 1963.
D.H. Huson . The generation and classification of tile-k-transitive tilings of the Euclidean plane, the sphere, and the hyperbolic plane. Geom. Dedicata, 47:269–296, 1993.
N. Johnson . Uniform Polytopes. Cambridge University Press, 2004.
R. Kenyon . The construction of self-similar tilings. Geom. Funct. Anal., 6:471–488, 1996.
R.B. Kershner . On paving the plane. Amer. Math. Monthly, 75:839–844, 1968.
R. Klitzing , M. Schlottmann , and M. Baake . Perfect matching rules for undecorated triangular tilings with 10-, 12-, and 8-fold symmetry. Internat. J. Modern Phys., 7:1453–1473, 1993.
O. Krötenheerdt . Die homogenen Mosaike n-ter Ordnung in der euklidischen Ebene, I. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 18:273–290, 1969.
J.C. Lagarias and P.W. Shor . Keller’s cube-tiling conjecture is false in high dimensions. Bull. Amer. Math. Soc., 27:279–283, 1992.
P.A. MacMahon . New Mathematical Pastimes. Cambridge University Press, 1921.
V.S. Makarov . On a nonregular partition of n-dimensional Lobachevsky space by congruent polytopes. Discrete Geometry and Topology, Proc. Steklov. Inst. Math, 4:103–106, 1992.
C. Mann . On Heesch’s Problem and Other Tiling Problems. Dissertation, University of Arkansas, Fayetteville, 2001.
P. McMullen . Convex bodies which tile space by translation. Mathematika, 27:113–121, 1980; 28:191, 1981.
H. Minkowski . Allgemeine Lehrsätze über die konvexen Polyeder. Nachr. Ges. Wiss. Göttingen. Math-Phys. Kl., 198–219, 1897. In Gesammelte Abhandlungen von Hermann Minkowski, reprint, Chelsea, New York, 1967.
H. Minkowski . Diophantische Approximationen. Teubner, Leipzig, 1907; reprinted by Chelsea, New York, 1957.
R.V. Moody . Mathematics of Long Range Aperiodic Order. NATO Advanced Science Institute Ser. C: Mathematical and Physical Sciences, 489, Kluwer, Dordrecht, 1997.
K. Reinhardt . Zur Zerlegung der euklidischen Räume durch kongruente Würfel. Sitzungsber. Preuss. Akad. Wiss. Berlin, 150–155, 1928.
D. Schattschneider . The plane symmetry groups: their recognition and notation. Amer. Math. Monthly, 85:439–450, 1978.
D. Schattschneider . Visions of Symmetry. Notebooks, Periodic Drawings, and Related Work of M.C. Escher. Freeman, New York, 1990.
D. Schattschneider and N. Dolbilin . One corona is enough for the Euclidean plane. In J. Patera , editor, Quasicrystals and Geometry, Fields Inst. Monogr. 10, Amer. Math. Soc., Providence, 1998, pages 207–246.
V. Schlegel . Theorie der homogen zusammengesetzen Raumgebilde. Verh. (= Nova Acte) Kaiserl. Leop.-Carol. Deutsch. Akad. Naturforscher, 44:343–459, 1883.
P. Schmitt . An aperiodic prototile in space. Manuscript, 1988.
E. Schulte . Tiling three-space by combinatorially equivalent convex polytopes. Proc. London Math. Soc., 49:128–140, 1984.
E. Schulte . Nontiles and nonfacets for Euclidean space, spherical complexes and convex polytopes. J. Reine Angew. Math., 352:161–183, 1984.
E. Schulte . Tilings. In P.M. Gruber and J.M. Wills , editors, Handbook of Convex Geometry, volume B, North Holland, Amsterdam, 1993, pages 899–932.
E. Schulte . Tilings. In R.A. Myers , editor, Encyclopedia of Physical Science and Technology, 3rd edition, Academic Press, New York, 2002, volume 16, pages 763–782.
M. Senechal . Color groups. Discrete Applied Math., 1:51–73, 1979.
M. Senechal . Which tetrahedra fill space? Math. Mag., 54:227–243, 1981.
M. Senechal . Color symmetry. Comput. Math. Appl., 16:545–553, 1988.
M. Senechal . Crystalline Symmetries. An Informal Mathematical Introduction. Adam Hilger, Bristol, 1990.
M. Senechal . Quasicrystals and Geometry. Cambridge University Press, 1995.
B. Solomyak . Nonperiodicity implies unique composition for self-similar translationally finite tilings. Discrete Comput. Geom., 20:265–279, 1998.
S. Stein and S. Szabó . Algebra and Tiling: Homomorphisms in the Service of Geometry. Volume 25 of Carus Math. Monographs. Math. Assoc. Amer., Washington, 1994.
B.A. Venkov . On a class of Euclidean polyhedra. Vestnik Leningrad. Univ. Ser. Mat. Fiz. Khim., 9:11–31, 1954.
G. Voronoi . Nouvelles applications des paramétres continus á la théorie des formes quadratiques II. J. Reine Angew. Math., 136:67–181, 1909.
T.W. Wieting . The Mathematical Theory of Chromatic Plane Ornaments. Marcel Dekker, New York, 1982.

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.