# Fractal Tilings Based on Successive Adjacent Substitution Rule

Authors: Peichang Ouyang; Xiaosong Tang; Kwokwai Chung; Tao Yu
Journal: Complexity
 (2018)

---

## Abstract

A fractal tiling orf-tiling is a tiling which possesses self-similarity and the boundary of which is a fractal. f-tilings have complicated structures and strong visual appeal. However, so far, the discovered f-tilings are very limited since constructing such f-tilings needs special talent. Based on the idea of hierarchically subdividing adjacent tiles, this paper presents a general method to generate f-tilings. Penrose tilings are utilized as illustrators to show how to achieve it in detail. This method can be extended to treat a large number of tilings that can be constructed by substitution rule (such as chair and sphinx tilings and Amman tilings). Thus, the proposed method can be used to create a great many of f-tilings.


---

## Body

## 1. Introduction

In many ways, the investigation of tilings is one of the most ancient parts of mathematics. They were considered by ancient Greeks and Muslim states to create decorative arts. In fact, the trace of tilings can be found in almost all ancient countries [1]. However, the rigorous mathematical study of tilings is comparatively recent, and many aspects of them remain unexplored [2]. With the deepening of research, the subject of tilings has become a vibrant branch of mathematics which shows a close relationship with algebra, combinatorics, cohomology, dynamical system, and so on [2–4].The traditional tiling is defined as a countable family of closed tiles which cover the Euclidean plane without gaps or overlaps. Compared conventional tilings, several families of tilings discovered by Fathauer are visually attractive [5–9]. Those tilings possess self-similarity and the boundary of which are fractals. Therefore, there exists an essential difference between this kind of tilings and conventional tilings. To avoid confusion with the standard definition of tilings that use standard fractals as tiles [10–14], such tilings are referred to as “f-tilings.”The combination of fractals and tilings has strong visual appeal. A glance off-tilings exhibited in Figure 1 might explain the reason very well. Moreover, arts based on f-tilings look more visually pleasing (see two designs demonstrated in Figure 2) [15]. Due to their aesthetic attraction, f-tilings have attracted much attention. For example, using matrix tool, Ouyang et al. developed a general way to derive the analytical expression of f-tilings’ dimension [16]. According to f-tilings’ symmetrical structures, [17, 18] established automatic algorithms to produce aesthetic patterns on two families of f-tilings (see examples shown in Figure 3).Figure 1
(a–c) Three examplesf-tilings. (d) Boundary details of (c).
(a)
(b)
(c)
(d)Figure 2
Two drawings based onf-tilings. Pictures are courtesy of Robert Fathauer.Figure 3
Two computer-generated aesthetic patterns based onf-tilings. The upper picture courtesy of H.M. Ma.
(a)
(b)Thoughf-tilings have apparent aesthetic value, so far, the discovered f-tilings are very limited. It can be understood that constructing f-tilings needs special talent. Does there exist a general method to create f-tilings. Well, we believe it is a quite attractive question. Here, we present a simple method that can be used to create a large number of f-tilings. We will use Penrose tilings to illustrate how to achieve it.The subject of Penrose tilings has attracted much attention since Roger Penrose discovered them [19] and has been investigated extensively [20]. It is a simple but remarkable tiling used in demonstrating aperiodicity. Refs. [21, 22] summarize the key progress and discovery related to aperiodic tilings. Through efforts of nearly half a century, an exciting progress of aperiodic tilings is the discovery of an aperiodic tiling which contains only one tile [21]. On the other hand, the aesthetic value of Penrose tilings has long been appreciated and remains a source of interest [15, 23]. In this paper, we propose a new method to explore its beauty.The rest of this paper is organized as follows. Section2 reviews the substitution rule of Penrose tilings. Based on the rule, Section 3 establishes a recursive algorithm to construct f-tilings. For tilings that can be generated by substitution rule (such as chair and sphinx tilings and Amman tilings), our method can be easily extended to them and create a great many of f-tilings. Section 4 attempts several ways to yield f-tilings and presents a gallery of the rich variety of f-tilings. Finally, conclusions are summarized in Section 5.


## 2. Substitution Rules of Penrose Tilings

There are several popular methods used in constructing Penrose tilings, such as substitution [2, 20, 24], projection [25, 26], and grid methods [26, 27]. For later application, we only introduce the substitution method. It works by taking a tile, or patch, expanding it, and then replacing the larger tiles by copies of the original tiles. The tiles are always replaced in the same way.Penrose tilings include three types: the original Penrose pentagonal tiling (P1), kite and dart tiling (P2), and rhombus tiling (P3). They have many common features. For example, in each case, the tiles are constructed from shapes related to the pentagon; in order to tile Euclidean plane aperiodically, the basic tiles need to be supplemented by matching rules. In particularly, P2 and P3 tilings have significant aesthetic appearance. For this reason, we only focus on the substitution method of P2 and P3 tilings. We start by recalling some basic terminologies.AtilingT in the Euclidean plane ℝ2 is a set of interior-closed tiles T1,T2,… such that tiles only intersect at boundaries and the union of all tiles constitutes the entire Euclidean plane ℝ2. A set S of tiles is called the protoset for T if any tile of T is congruent to a tile of S. Assume T is a tiling of protoset S, then we say SadmitsT. A tiling is called edge to edge if corners and sides of the tiles coincide with the vertices and edges of the tiling. A tiling T is said to be nonperiodic if it admits no translations. A protoset is said to be aperiodic if it admits only nonperiodic tilings. A tiling with aperiodic protoset is called aperiodic tiling.Penrose tilings are the best-known examples of aperiodic tilings. It could be easily constructed by means of substitution rule. A substitution rule is defined by three components: first, a protosetS; second, an expansion constant ϑ>1; last, partition rules with respect to the inflated prototiles of S so that the subdivided smaller tiles congruent to the tiles of S.For clarity, the substitution rules of P2 and P3 tilings are described separately in Subsection2.1 and Subsection 2.2.


### 2.1. Substitution Rules of P2 Tiling Admitted by Kite and Dart Tiles

The protoset of P2 tiling has the following two kinds of tiles:(i)
Kite: a quadrilateral with four interior angles which are2π/5, 2π/5, 2π/5, and 4π/5. Two sides of length τ=5+1/2 and two sides of length 1, as shown in the left of Figure 4(a).
(ii)
Dart: a nonconvex quadrilateral with four interior angles which areπ/5, 2π/5, π/5, and 6π/5, as shown in the right of Figure 4(a).Figure 4
(a) Kite and dart prototiles used in constructing P2 tiling. (b) Partition rules ofA-tile and B-tile associated with P2 tiling.
(a)
(b)The kite and dart tiles may be bisected along their symmetrical axes to form two pairs of triangles. The larger acute triangle is calledA-tile, in which there are two sides of length τ and one side of length 1, referring to the left of Figure 4(a). The smaller obtuse triangle is called B-tile, in which there are two sides of length 1 and one side of length τ, referring to the right of Figure 4(a). Each vertex of A-tile or B-tile is marked with either a small solid or an open circle. A monochromatic edge is an oriented edge connecting two vertices of the same kind of circle.To construct P2 tiling, kite and dart tiles must be arranged by the following matching rules: (1) the circle type of a vertex must be the same; (2) edges of the same length must be put together; (3) the monochromatic edges of adjacent tiles must be oriented in the same direction. In practice, directly using matching rules to construct a P2 tiling is very difficult. We subsequently describe successive inflation and substitution method to achieve it.Place anA-tile (B-tile) on the Descartes coordinate system as shown in Figure 5(a) (Figure 5(d)). (1) Inflate the A-tile (B-tile) τ times as τA-tile (τB-tile). (2) Use the substitution rule shown in the left of Figure 4(b) (the right of Figure 4(b)) to subdivide the inflated tile, which gives raise to the result of Figure 5(b) (Figure 5(e)). (3) First, reflect A-tile (B-tile) about the x-axis, then repeatedly rotate it about the origin of 2π/5 to form a ten-sided regular polygon (star-shaped polygon). (4) Successive inflation and substitution of patches of tiles will eventually tile Euclidean plane ℝ2. (5) A P2 tiling is obtained by deleting the monochromatic edges which appeared in the process of successive inflation and substitution. Figure 5 demonstrates the first and second inflation and substitution processes with respect to A-tile and B-tile of P2 tiling. The left of Figure 6 shows a P2 tiling obtained in this manner.Figure 5
(a–c) The first and second inflation and substitution processes of theA-tile associated with P2 tiling. (d–f) The first and second inflation and substitution processes of the B-tile associated with P2 tiling.
(a)
(b)
(c)
(d)
(e)
(f)Figure 6
(a) A P2 tiling constructed by kite and dart tiles. (b) A P3 tiling constructed by thin and thick rhombuses.
(a)
(b)The difference of usingA-tile or B-tile is that, during the successive inflation and substitution, the center of a P2 tiling will alternately appear a ten-sided regular polygon or star-shaped polygon.


### 2.2. Substitution Rules of P3 Tiling Admitted by Thin and Thick Rhombuses

The protoset of P3 tiling comprises a pair of rhombuses with equal sides of lengthτ but different angles:
(i)
Thin rhombus: a rhombus which has four corners with angles ofπ/5, 4π/5, π/5, and 4π/5, as shown in the left of Figure 7(a).
(ii)
Thick rhombus: a rhombus which has the angles of2π/5, 3π/5, 2π/5, and 3π/5, as shown in the right of Figure 7(a).Figure 7
(a) Thin and thick rhombus prototiles used for constructing P3 tiling. (b) Partition rules ofA-tile and B′-tile associated with P3 tiling.
(a)
(b)These two rhombuses can also be bisected along their symmetrical axes to form two pairs of triangles which are the same as the case of P2 tiling. Again, the larger acute triangle is denoted asA-tile, but the smaller obtuse triangle is denoted as B′-tile. Each vertex of A-tile or B′-tile is marked with either a small solid or an open circle. A monochromatic edge is an oriented edge connecting two vertices of the same kind of circle.The partition rules associated withA-tile and B′-tile are exhibited in Figure 7(b). The right of Figure 6 illustrates a P3 tiling. To save space, we omit matching rules and construction method of P3 tiling since it is completely similar to P2 tiling.


## 2.1. Substitution Rules of P2 Tiling Admitted by Kite and Dart Tiles

The protoset of P2 tiling has the following two kinds of tiles:(i)
Kite: a quadrilateral with four interior angles which are2π/5, 2π/5, 2π/5, and 4π/5. Two sides of length τ=5+1/2 and two sides of length 1, as shown in the left of Figure 4(a).
(ii)
Dart: a nonconvex quadrilateral with four interior angles which areπ/5, 2π/5, π/5, and 6π/5, as shown in the right of Figure 4(a).Figure 4
(a) Kite and dart prototiles used in constructing P2 tiling. (b) Partition rules ofA-tile and B-tile associated with P2 tiling.
(a)
(b)The kite and dart tiles may be bisected along their symmetrical axes to form two pairs of triangles. The larger acute triangle is calledA-tile, in which there are two sides of length τ and one side of length 1, referring to the left of Figure 4(a). The smaller obtuse triangle is called B-tile, in which there are two sides of length 1 and one side of length τ, referring to the right of Figure 4(a). Each vertex of A-tile or B-tile is marked with either a small solid or an open circle. A monochromatic edge is an oriented edge connecting two vertices of the same kind of circle.To construct P2 tiling, kite and dart tiles must be arranged by the following matching rules: (1) the circle type of a vertex must be the same; (2) edges of the same length must be put together; (3) the monochromatic edges of adjacent tiles must be oriented in the same direction. In practice, directly using matching rules to construct a P2 tiling is very difficult. We subsequently describe successive inflation and substitution method to achieve it.Place anA-tile (B-tile) on the Descartes coordinate system as shown in Figure 5(a) (Figure 5(d)). (1) Inflate the A-tile (B-tile) τ times as τA-tile (τB-tile). (2) Use the substitution rule shown in the left of Figure 4(b) (the right of Figure 4(b)) to subdivide the inflated tile, which gives raise to the result of Figure 5(b) (Figure 5(e)). (3) First, reflect A-tile (B-tile) about the x-axis, then repeatedly rotate it about the origin of 2π/5 to form a ten-sided regular polygon (star-shaped polygon). (4) Successive inflation and substitution of patches of tiles will eventually tile Euclidean plane ℝ2. (5) A P2 tiling is obtained by deleting the monochromatic edges which appeared in the process of successive inflation and substitution. Figure 5 demonstrates the first and second inflation and substitution processes with respect to A-tile and B-tile of P2 tiling. The left of Figure 6 shows a P2 tiling obtained in this manner.Figure 5
(a–c) The first and second inflation and substitution processes of theA-tile associated with P2 tiling. (d–f) The first and second inflation and substitution processes of the B-tile associated with P2 tiling.
(a)
(b)
(c)
(d)
(e)
(f)Figure 6
(a) A P2 tiling constructed by kite and dart tiles. (b) A P3 tiling constructed by thin and thick rhombuses.
(a)
(b)The difference of usingA-tile or B-tile is that, during the successive inflation and substitution, the center of a P2 tiling will alternately appear a ten-sided regular polygon or star-shaped polygon.


## 2.2. Substitution Rules of P3 Tiling Admitted by Thin and Thick Rhombuses

The protoset of P3 tiling comprises a pair of rhombuses with equal sides of lengthτ but different angles:
(i)
Thin rhombus: a rhombus which has four corners with angles ofπ/5, 4π/5, π/5, and 4π/5, as shown in the left of Figure 7(a).
(ii)
Thick rhombus: a rhombus which has the angles of2π/5, 3π/5, 2π/5, and 3π/5, as shown in the right of Figure 7(a).Figure 7
(a) Thin and thick rhombus prototiles used for constructing P3 tiling. (b) Partition rules ofA-tile and B′-tile associated with P3 tiling.
(a)
(b)These two rhombuses can also be bisected along their symmetrical axes to form two pairs of triangles which are the same as the case of P2 tiling. Again, the larger acute triangle is denoted asA-tile, but the smaller obtuse triangle is denoted as B′-tile. Each vertex of A-tile or B′-tile is marked with either a small solid or an open circle. A monochromatic edge is an oriented edge connecting two vertices of the same kind of circle.The partition rules associated withA-tile and B′-tile are exhibited in Figure 7(b). The right of Figure 6 illustrates a P3 tiling. To save space, we omit matching rules and construction method of P3 tiling since it is completely similar to P2 tiling.


## 3.f-Tilings from Successive Adjacency Substitution Method

Letλ be a patch of tiles created by successively inflating and substituting B′-tile of P3 tiling 3 times. Figure 8(a) shows an initial frame Γ obtained by first reflecting λ about the x-axis and then rotating it about the origin repeatedly by 2π/5. Remember that the resulting Γ is constructed by A-tile and B′-tile, instead of the thin and thick rhombuses.Figure 8
(a)Γ is a patch of tiles with the dihedral group D5 symmetry, which will be used as initial frame to generate f-tiling. (b) By vertex adjacency substitution rule, the first four generations of the f-tiling on Γ. (c) The first four generations of the f-tiling on Γ obtained by moving the initial frame Γ.
(a)
(b)
(c)We next utilizeΓ as the initial seed to produce a f-tiling T. The first four layers of T are displayed in Figure 8(b). Combined with Figure 8(c), we summarize the recursive algorithm as follows.Step 1.
Denote by 1st-layer tiles (the biggest white and green tiles in the figure) as tiles in the center ofΓ. Except for 1st-layer tiles, denote by ∑1 tiles as the other tiles of Γ.Step 2.
All∑1 tiles are substituted once by the substitution rule. Denote by 2nd-layer tiles (the yellow and white tiles in the figure) as the substituted smaller tiles contained in the previous ∑1 tiles adjacent to 1st-layer tiles. Except for the 2nd-layer tiles, denote by ∑2 tiles as the other substituted tiles contained in ∑1 tiles.Step 3.
All∑2 tiles are substituted once by the substitution rule. Denote by 3rd-layer tiles (tiles with bold black edges in the figure) as the substituted smaller tiles contained in the previous ∑2 tiles adjacent to the 2nd-layer tiles. Except for 3rd-layer tiles, denote by ∑3 tiles as the other substituted tiles contained in ∑2 tiles.Step 4.
All∑3 tiles are substituted once by the substitution rule. Denote by 4th-layer tiles (the outmost tiles with red or blue edges in the figure) as the substituted smaller tiles contained in the previous ∑3 tiles adjacent to the 3rd-layer tiles. Except for 4th-layer tiles, denote by ∑4 tiles as the other substituted tiles contained in ∑3 tiles.Step 5.
All∑i tiles are substituted once by the substitution rule. Denote by (i + 1)th-layer tiles as the substituted smaller tiles contained in the previous ∑i tiles adjacent to the ith-layer tiles. Except for (i + 1)th-layer tiles, denote by ∑i+1 tiles as the other substituted tiles contained in ∑i tiles, i=4,5,6,….Keep in mind the three points. First, for the case shown in Figure8, two tiles are adjacent which means that they have one vertex in common. Second, tiles of i-layer and ∑i always have the same level size. Last, all known f-tilings are edge to edge, while f-tilings constructed by above method are not edge to edge.According to the recursive algorithm, for a given initial tile frameΓ, once we appoint 1st-layer tiles, the rest of the tiles of Γ form ∑1 tiles automatically. By vertex adjacency rule and successive substitutions, we can obtain two sequences i−layertiles,i=1,2,3,… and ∑itiles,i=1,2,3,…. Geometrically, the sequences correspond to a hierarchical tiling. When i→+∞, the resulting tiling becomes a fractal. For convenience, we call the generation method of such f-tilings as successive adjacency substitution method.


## 4. Gallery off-Tilings from Successive Adjacency Substitution Method

In this section, we implement some cases and present a gallery of the rich variety off-tilings obtained by successive substitution method.Letλ be a tile created by successively inflating and substituting the prototile T of P2 or P3 tiling n times, and let Γ be the initial tile frame obtained by first reflecting λ about the x-axis and then rotating it about the origin repeatedly of 2π/5. By successive adjacency substitution method described in Section 3, we denote by TP,T,n tiling as the f-tiling generated by seed Γ.As a tiling based on seedΓ generates, the amount of calculation will rise sharply. Most of f-tilings were produced through 10 to 15 generations, which adequately illustrates fractal appearance. To show some interesting details, we usually zoomed in some parts of a f-tiling.Figure9 exhibits a T(P3,A-tile,5) tiling as well as its boundary details. We see an interesting phenomenon that, as generations continue, the regions marked “F” will be gradually closed and fully filled. In practice, two factors determine the closeness of a region: the size of the region and the scale of contraction factor. For example, for the f-tilings shown in Figures 10 and 11 that both gradually reduce from the outside toward the center, the center region of Figure 10 will not be filled. However, the center region of Figure 11 do close up since the region is small enough.Figure 9
(a) AT(P3,A-tile,5) tiling. (b) From left to right, boundary details of the seventh, eighth, and tenth generations. As generations continue, the regions marked “F” will be gradually closed and fully filled.
(a)
(b)Figure 10
AT(P2,A-tile,3) and its center details obtained by appointing the outermost colored tiles as 1st-layer tiles.
(a)
(b)Figure 11
AT(P3,A-tile,2) and its center details obtained by appointing the outermost green tiles as 1st-layer tiles.
(a)
(b)Figure12 illustrates another similar case. Figure 13 demonstrates two interesting f-tilings that present a perfect circular outline. The enlarged boundary details show that both f-tilings have neat hierarchical structure. It should be noted that, according to the Penrose rules, no “star” made of 10 acute triangles appear in an infinite Penrose tiling. The center “star” patch of the left of Figure 13 is constructed by copying and rotating a cute triangle 10 times, rather than by inflating and subdividing a tile of the Penrose tiling.Figure 12
(a) AT(P3,A-tile,4) tiling. (b) From left to right, boundary details of the sixth, seventh, eighth, and ninth generations. As generations continue, the regions marked “G” will be closed gradually and fully filled.
(a)
(b)Figure 13
AT(P2,A-tile,3) with ten-sided regular polygon at the center (a) and a T(P2,A-tile,4) with star-shaped polygon at the center (b). The enlarged boundary details show hierarchical fine structure.
(a)
(b)The previousf-tilings are obtained by appointing the central tiles as 1st-layer tiles. By successive adjacency substitution method demonstrated in Figure 8, tiles will gradually reduce from the center toward the outside. Conversely, we may appoint the outermost tiles as 1st-layer tiles. Under this situation, as generations continue, tiles will gradually reduce from the outside toward the center. Figures 10 and 11 illustrate two such examples, where the initial seed Γ are marked with yellow lattices, the outermost colored tiles are appointed as 1st-layer tiles, and the enlarged parts show tilings’ center details.We may also appoint some middle tiles of initial seedΓ as 1st-layer tiles and create f-tilings on such seeds. Under this situation, tiles will gradually reduce from the middle toward both center and outside. Figure 14 illustrates an example in which the middle yellow 1st-layer tiles form a ring. By appointing a few sporadic middle tiles as 1st-layer tiles, Figure 15 shows two other kinds of such f-tilings.Figure 14
AT(P2,B-tile,4) and its center and boundary details obtained by appointing the middle yellow tiles as 1st-layer tiles.Figure 15
(a) AT(P3,B-tile,4) tiling in which the middle green tiles are appointed as 1st-layer tiles. (b) A T(P2,A-tile,4) tiling in which the middle gray tiles are appointed as 1st-layer tiles.
(a)
(b)One thing that needs to be paid special attention is the meaning of adjacency. In the case of Figure8, two tiles are adjacent means that they have one vertex in common. We may call such f-tilings as point adjacency f-tilings. Similarly, we can also define adjacency that two tiles have one edge in common and call such f-tilings as edge adjacencyf-tilings.According to edge adjacency rule, using similar successive adjacency substitution method, we can create different stylef-tilings. Due to space constraint, at the end of this paper, we only exhibit two edge adjacency examples. By appointing the center tiles of the initial seed Γ as 1st-layer tiles, Figure 16 demonstrates two edge adjacency f-tilings.Figure 16
(a) An edge adjacencyT(P2,B-tile,3) tiling and its boundary details. (b) An edge adjacency T(P3,A-tile,3) tiling and its boundary details.
(a)
(b)


## 5. Conclusion

In this paper, based on the idea of hierarchically subdividing adjacent tiles, we present a general method to createf-tilings. Penrose P2 and P3 tilings are utilized as illustrators.We first review the substitution rules for constructing P2 and P3 tilings. Then, we present a recursive algorithm to generatef-tilings by hierarchically subdividing adjacent tiles, which include six steps: (1) use an A-tile or B-tile (B′-tile) and substitution rule to construct a patch of tiles with the dihedral group D5 symmetry; (2) denote some tiles in the patch as the 1st-layer tiles and denote all remainder tiles as ∑1 tiles; (3) all ∑i tiles are substituted once by the substitution rule; (4) denote by i+1th-layer tiles as the substituted smaller tiles contained in the previous ∑i tiles adjacent to ith-layer tiles; (5) except for the i+1th-layer tiles, denote by ∑i+1 tiles as the other substituted tiles contained in ∑i tiles; (6) let i=1,2,3,…. By appointing ∑i+1 tiles and i+1th-layer tiles, a f-tiling is generated by recursively executing steps (3)–(5).With the method of hierarchically subdividing adjacent tiles, we implement three cases by appointing the center, outer, and middle tiles of the patch as the 1st-layer tiles, respectively. Accordingly, tiles of the resultingf-tilings gradually reduce from the center toward the outer (Figures 9, 12, and 13), from the outside toward the center (Figures 10 and 11), and from the middle toward both center and outer (Figures 14 and 15). Figures 9–15 are produced by the vertex adjacent rule which means that two tiles are adjacent if they have more than one vertex in common. This method can be similarly generalized to edge adjacent rule which means that two tiles are adjacent if they have two vertexes in common. We attempt two f-tilings of edge adjacent kind and demonstrate them in Figure 16. It is obvious that our method can be extended to treat a large number of tilings that can be constructed by substitution rule and used to yield a great many of f-tilings.



---

*Source: 6451921-2018-07-15.xml*