A self-affine tile is a two-dimensional set satisfying an expansion identity that allows tiling images to be generated. In this article, we discuss the generation of such images paying particular attention to the boundary of the set, which frequently displays a fractal structure.

Introduction

A tile is a bounded subset of the plane, copies of which may be used to cover the whole plane without gaps or overlap. There are many sources (such as [1]) of beautiful images involving tiling, from medieval Islamic art, through Escher, to more modern work. Perhaps the simplest example of a tile, though, is a solid square, which may tile the plane in a familiar checkerboard pattern. The square is also an example of an important subclass of tiles called the self-affine tiles. A tile is self-affine if there is an expanding matrix and a collection of vectors (called the digit set) such that

(1)

where the pieces in the union are assumed to intersect only in their boundaries. Here is the image of under multiplication by the matrix . Note that if is a self-affine tile with respect to and , then is a self-affine tile with respect to and . Thus, iteration of equation (1) yields arbitrarily large tiling images. The unit square is an example of a self-affine tile where

(2)

Iteration of equation (2) yields the checkerboard pattern.

As we will see, self-affine tiles of surprising intricacy may be generated using the notion of an iterated function system (IFS) from fractal geometry. For example, the image in Figure 1 is a self-affine four-tile (i.e., it consists of four parts) corresponding to the matrix and digit set

(3)

This text is the heading of a closed group that sets up definitions.

Figure 1. A self-affine four-tile.

Constructing interesting images is greatly simplified by the existence of fairly simple rules dictating possible choices for the matrix and digit set . Also of interest is the boundary between the constituent parts. The boundary of a self-affine tile frequently has a fractal structure and may be generated and analyzed using a generalized notion of an IFS. The boundary of the four-tile, for example, may be shown to have a fractal dimension of .

Self-Affine Sets and Tiling

Self-similarity and iterated function systems are, by now, fairly well-known concepts. See, for example, [2, 3] for a general introduction or [4, 5], which describe implementations using Mathematica. Here, we briefly define our terms to establish notation and clarify important results.

Roughly speaking, a set is called self-similar if it is composed of two or more sets geometrically similar to the whole. Self-similarity is more rigorously defined and analyzed using an important tool called an iterated function system, or IFS. An IFS is simply any finite collection of contractive mappings of the plane. Associated with an IFS there is always a unique nonempty, closed, bounded set satisfying

(4)

The set defined in equation (4) is called the invariant set or attractor of the IFS. The functions in an IFS describe the exact relationship between the invariant set and its constituent parts. If the IFS consists entirely of contractive similarities, then is called self-similar. If the IFS consists of affine functions, then is called self-affine.

Self-affine sets have played an important role in the development of fractal geometry in part because they provide a dazzling class of images, even though affine functions are very easy to describe and implement on a computer. Thus, it takes a small amount of information to store very interesting images. In Mathematica (in particular, in the packages described here), an affine function may be represented as , where A is a two-dimensional matrix and b is a shift vector. The following code represents an IFS for the unit square.

In order to generate an image of the square, we use the ShowIFS command defined in the IFS package. The implementation of the ShowIFS command is similar to commands described in [4, 5].

Figure 2. A square generated from an IFS.

In the ShowIFS command, the second argument (9 in this case) indicates the depth of the approximation. Thus, the image consists of points distributed over the unit square. A large number of points is typically required, as we want to fill a two-dimensional region. The Color option is nice when investigating tiles to highlight the constituent parts. When Color is set to True, the Colors option may be set to Automatic (the default), in which case the Hue function is used to generate a spectrum of colors, or Colors may be set to a list of colors.

Now, a self-affine tile is also a self-affine set. If a self-affine tile satisfies equation (1), then after applying to both sides we see that

(5)

In fact, this is the exact relationship between the description of the square as a self-affine tile given by equations (2) and the IFS defined by squareIFS; it is easy to pass from one description to the other. The major question now is how to choose a matrix and digit set to generate interesting images. A beautiful theorem, published by Christoph Bandt [6], provides an answer. This theorem is also described in [7] at a more elementary level.

An expansive matrix is simply a matrix whose eigenvalues are all larger than one in absolute value. The terminology residue system and digit set originates from work by Gilbert [8] describing certain self-similar sets in terms of number representation in the complex plane. By definition, a residue system for is a complete set of coset representatives for the quotient group . While this definition is abstract, it is fairly easy to describe how to construct a residue system. Given the matrix , denote its column vectors by and . The simplest residue system for consists of those points with integer coordinates lying inside the parallelogram determined by and and including only the two sides containing the origin. For example, the following figure illustrates this simple digit set for the matrix

We may construct other residue systems from this simple one as follows: two integer points are said to be equivalent if their difference is a linear combination of and . Any vector from our simple residue system may be replaced by another from its equivalence class; that is, starting from our simplest residue system, we may simply shift some of its members by some linear combination of and to obtain another residue system. A digit set which forms a residue system for is called a standard digit set. Note that the shift of a standard digit set by an integer vector is again a standard digit set; thus, we may suppose that the zero vector is one of the digits. Some of our package functions use this simplifying assumption, so it is best to use digit sets containing the origin.

Let us demonstrate how easy it is to generate interesting self-affine tiles using this theorem. We first describe a simple modification of the square’s IFS. We use the same matrix, a simple expansion by the factor 2, but we replace one of the digits by a shift. In particular, we shift the digit by to obtain . We use the substitution operator to translate the digit set and matrix into the modified IFS.

Figure 3. A “minor” modification of Figure 2.

This simple modification is already interesting and the result is difficult even to recognize as a tile. We can get an inkling of how it might tile by examining all shifts of the set by the digit set.

Our next example is called the “twin dragon” and is defined by the following matrix.

Note that the determinant of this matrix is 2. In general, the absolute value of the determinant indicates the number of pieces constituting the tile. This is because the union on the right of equation (1) increases the area of by the factor , while the matrix on the left side of equation (1) increases the area of by the factor . Thus, in this case, our digit set will have two elements. Using the column vectors, it is easy to determine the simplest digit set.

Now we translate this matrix and digit set to an IFS, as in the previous example.

Here is the result.

Figure 4. The twin dragon.

The rotation induced by the matrix , and therefore by , makes it slightly more difficult to see how equation (1) is satisfied. In Figure 5, we see the image of Figure 4 under the mapping . The red part of the twin dragon has clearly mapped onto the whole original twin dragon, while the gray part has mapped onto the original shifted to the right one unit.

Figure 5. The image of Figure 4 under the mapping .

Digraph Iterated Function Systems

Before examining more examples, we turn to the question of how to highlight the boundary between the parts. It turns out that the boundary of a self-affine tile may be generated by a generalized type of IFS called a digraph iterated function system. To illustrate this concept, consider the two curves and . The curve is composed of one copy of itself, scaled by the factor , and two copies of , rotated and scaled by the factor . is composed of one copy of itself, scaled by the factor , and one copy of , reflected and scaled by the factor .

This text is the heading of a closed group that sets up definitions.

In general, digraph self-similarity is exhibited by a family of sets . Each set is composed of parts which are scaled images of sets chosen from the collection. A digraph IFS is a matrix whose elements are lists of affine functions. The elements in row indicate how the set is composed. Thus, the element in row and column should be a list of affine functions mapping into . The analog of equation (4) for a digraph IFS is

(6)

As with an IFS, the list of sets is uniquely determined by the digraph IFS. The curves and may be generated using a digraph IFS, which is represented as follows.

The RotationMatrix function is defined for all of the FractalGeometry packages. The DigraphFractals package also defines the command ShowDigraphFractals, which may be used to generate the curves.

The terminology digraph fractal arises from a description of the combinatorics involved using directed multigraphs. A directed multigraph consists of a finite set of vertices and a finite set of directed edges between vertices. We use the terminology multigraph because we allow more than one edge between any two vertices. Figure 6 depicts the digraph for the curves and . There are two edges from node to node and one edge from node to itself, since consists of two copies of with one copy of itself. Similarly, there is one edge from node to node and one edge from to itself, since consists of one copy of together with one copy of itself.

This text is the heading of a closed group that sets up definitions.

Figure 6. The digraph for the curves and .

A path through a digraph is a finite sequence of edges such that the terminal vertex of any edge is the initial vertex of the subsequent edge. The digraph is called strongly connected if, for every pair of vertices and , there is a path from to . The concept of strong connectivity is important to understand for the following reason: as with a standard IFS, there are two common algorithms for generating images using a digraph IFS; one algorithm is stochastic and the other deterministic. The stochastic algorithm works only when the digraph is strongly connected, while the deterministic algorithm works whether the digraph is strongly connected or not. For the purposes of this article, the stochastic algorithm typically works better but, as we will see, it is not always applicable.

The DigraphFractals package is fully described in [9] along with more complete descriptions of the theory and implementation.

The Boundary of a Tile

Now we wish to use the digraph IFS scheme to describe the boundary of a self-affine tile. The following technique was published in [10]. Suppose that is a self-affine tile and there is a lattice of points in the plane so that the translates of by the points of form a tiling of the plane. The lattice should be invariant under the action of in the sense that . (Note that the lattice condition is frequently, but not always, satisfied.) Given , define . The boundary of is formed by the collection of sets that are nonempty, excluding the case . It turns out that these sets are digraph self-affine; that is, if we let , then the collection forms the invariant list of a digraph IFS. This can be demonstrated by examining how the expansion matrix affects each set and then translating to a digraph IFS by applying :

(7)

We are only interested in the nonempty intersections, so, given and in , let denote the set of pairs of digits so that . Then, applying to both sides of equation (7), we see that

(8)

Equation (8) defines a digraph IFS to generate the sets . Given and in , the functions mapping into are precisely those affine functions defined by for all digits so that there is a digit satisfying .

We now implement these ideas to generate the boundary of the twin dragon. We first define A and .

We also need to know the set . In general, it can be difficult to determine . Fortunately, [10] describes an algorithm to automate the procedure. The algorithm is fairly difficult, however, and the technique seems rather far removed from the other techniques described here. Thus, we refer the interested reader to [10] and the code defining the NonEmptyShifts function in the SelfAffineTiles package. Examining Figure 4, it is not too difficult to see that the correct set of vectors for the twin dragon is defined as follows.

The following code illustrates the six translates of the twin dragon and colors them so that they are easy to distinguish.

Figure 7. Translates of the twin dragon defining the boundary.

The original twin dragon from Figure 4 is the central white region in Figure 7. The six pieces of the boundary are the boundaries between the white region and the six colored shifted regions.

Now, for each pair where and are chosen from , we want to denote the set of pairs of digits so that . This can be accomplished as follows.

In order to make sense of this, let us look at the length of each element of the matrix.

This matrix is called the substitution matrix of the tile and tells us simply the combinatorial information of how the pieces of the boundary fit together. Reading the rows, for example, we see that the first piece is composed of one copy of the last piece, the second piece is composed of one copy of itself and two copies of the first, and so on. Note also that the order of the rows and columns is dictated by the order of the set . Thus, the first piece refers to the boundary along the maroon image in the lower left of Figure 7, since is the first shift vector in the set . The subsequent pieces are numbered counterclockwise around the central tile, since that is the way that is set up.

We can transform the digitPairsMatrix into a digraph IFS defining the boundary by simply replacing each pair with the affine function .

To see how it worked, we will use the function ShowDigraphFractalsStochastic defined in the DigraphFractals package. This stochastic algorithm frequently seems to work better for this particular task than the deterministic version defined by ShowDigraphFractals. We will use color to distinguish the constituent parts.

We can collect all of the pieces to form the entire boundary.

We can display the boundary with the original image of the twin dragon.

Note that we have outlined the boundary of the entire set. If we would like to highlight the boundaries of the constituent parts, we need simply to feed the boundary to the ShowIFS command using the boundaryPoints as an option to Initiator.

More Examples

The algorithms described are encapsulated in the package SelfAffineTiles. We load the package and use it to look at many more examples.

The main graphical command which ties all of the previous algorithms together is the ShowTile command. accepts the matrix A and generates an approximation to the corresponding self-affine tile to level depth. The boundary is automatically generated and the parts are colored differently.

Figure 8. A self-affine three-tile.

The ShowTile command accepts the option DigitSet. When DigitSet is set to the default of Automatic, ShowTile calls the BaseDigitSet function to compute the simple digit set described previously. We can illustrate this simple digit set using the command ShowBaseDigitSet.

We can also look at the tiles generated by alternative digit sets using the DigitSet option. In the following, we subtract the first column vector of , , from the digit to obtain the shifted digit .

Figure 9. A self-affine three-tile using an alternative digit set.

The tiles in Figures 8 and 9 consist of three pieces, since . Three-tiles are more diverse than two-tiles, as we have more flexibility in choosing the matrix and relative positions of the digits. Here is another three-tile using a different matrix.

Figure 10. Another self-affine three-tile.

The examples in this section so far have been self-affine but not self-similar. Sometimes, such a set is affinely equivalent to a self-similar set. In this case, the self-similar set will correspond to the same matrix and digit set expressed in another basis. As explained in [7], if has a pair of complex conjugate eigenvalues, then is similar (i.e., conjugate) to a similarity matrix. In this case, we may find the change of basis matrix as follows. Suppose that the vector

is an eigenvector for , and let be the inverse of the matrix

Then, will be a similarity transformation. The self-affine tile shown in Figure 10 falls into this case, as the following computation shows.

We can now find one of the corresponding eigenvectors.

And we can use this to find the change of basis matrix .

The matrix should conjugate to a similarity matrix.

We can see that does indeed induce a similarity transformation. In fact, it is simply a clockwise rotation throughout the angle together with an expansion of .

Now the point is that, while this last matrix does not have integer entries, so it does not seem to fall into the scheme outlined by Bandt’s theorem, it may be expressed as a matrix with integer entries with respect to the correct choice of basis. In fact, if we choose our basis to be the column vectors of , then this similarity is expressed as the matrix . The statement and proof of Bandt’s theorem are essentially algebraic, so the choice of basis does not affect the result. The ShowTile function accepts the option Basis, which assumes that the matrix is expressed with respect to the given basis. If we rerender the tile defined by with respect to this new basis, we generate a self-similar set.

When is conjugate to a similarity, the fractal dimension of the boundary may be calculated by the formula , where is the spectral radius of the substitution matrix and is the spectral radius of . (The spectral radius is simply the largest of the absolute values of the eigenvalues.) This formula is encoded in the package function BoundaryDimension. For example, here is the dimension of the boundary of the previous tile.

A change of basis can be useful even if the matrix is already a similarity matrix. For example, the self-similar tile of Figure 3 may be expressed in another basis to yield the tile in Figure 11, which has three-fold rotational symmetry. Note that the matrix and digit set have not changed; only the Basis option has been added. Also notice that the ShowTile command accepts a Colors option, which is similar to the Colors option for the ShowIFS command.

Figure 11. A self-similar four-tile with three-fold rotational symmetry.

We will explain the warning message in the next section, although it does not appear to have genuinely caused a problem in this case.

As a final example, we generate Gosper’s famous snowflake.

Note that Gosper’s flake was also generated using the change of basis technique, as was the tile shown in Figure 1.

Potential Problems and Tricks

There are subtle difficulties that may arise when generating images of self-affine tiles, particularly when dealing with the boundary. In this section, we outline some of the tricks that the SelfAffineTiles package provides to assist in dealing with these potential problems.

First, it should be understood that many tiling pictures are simply not very attractive. In fact, a randomly chosen digit set is not likely to generate a nice image. Those who play with the package are likely to find several such examples.

Even when the image is quite attractive, subtle issues can arise with the boundary. One of the most important issues is that the digraph describing the boundary may not be strongly connected. In this case, the stochastic algorithm to generate the boundary might not be effective. This situation arises in the simplest of examples, that of the unit square. Let us try to generate the unit square as simply as possible.

For example, the following command will lead to trouble. (The cell is therefore given the setting Evaluatable → False.)

The ShowTile command recognizes that the boundary digraph IFS is not strongly connected and suggests two possibilities. Let us follow the first suggestion.

In fact, it is frequently a good idea to set when experimenting with ShowTile if you do not know what to expect.

Next, we try the second suggestion.

Now an approximation to the boundary has been generated, but this took considerably longer than the previous command to yield a fairly poor image of the boundary. In this case, an understanding of the boundary digraph IFS allows us to refine it and improve the performance. The SelfAffineTiles package contains several functions to assist us. First, we look at the substitution matrix of the tile.

This tells us that the boundary consists of eight pieces. Note that the first and last pieces each consist of one copy of themselves, while the third and fifth pieces each consist of one copy of the other. Such simple parts of the digraph IFS will generate single points and, in fact, these parts correspond to the vertices of the square. We can verify this by examining the shift set used by the program.

Indeed, the first portion of the boundary is simply , where is the unit square. Of course, this intersection is simply the vertex at the origin. We may generate the entire boundary using only the shifts , , , and . This will make the boundary digraph IFS much smaller and speed up the rendering of the boundary considerably. This approach can be implemented using the Shifts option.

Note how much faster this image was generated, even though the greater Depth has rendered the boundary in much more detail. We can use the SubstitutionMatrix command to look at the new substitution matrix for the boundary.

It appears that the new boundary digraph IFS is not strongly connected either, so we still could not use the stochastic algorithm for the boundary. We can use the StronglyConnectedBoundaryQ command to verify this.

Finally, we outline a technique to generate the boundary of what appears to be the most challenging type of situation (with the exception of tiles simply consisting of a very large number of pieces). Lagarias and Wang [11, 12] carry out a careful analysis of how self-affine tiles can tile the plane and prove that every self-affine tile does indeed tile using translates chosen from some lattice. However, that lattice need not be invariant, meaning that the technique of [10], which we have implemented here, might not work. The work of Lagarias and Wang shows that frequently the lattice can be chosen to be the lattice generated by and, if so, that lattice will be invariant. In fact, that is exactly the lattice generated by the SelfAffineTiles package using the LatticeReduce command. They also outline a special case where this might not work and call such an example a stretched tile (since its area is too large to tile by the usual lattice). The basic example of a stretched tile is defined by the matrix and digit set given here.

The lattice as described is the integer lattice in this example.

As we shall see by simply generating the tile, however, its area is too large to tile via shifts by the integer lattice. In fact, the area of this tile is 3, while any set which tiles via the integer lattice must have an area of only 1.

Note that the boundary is not complete. Of course, we did not really expect this to work. We can, however, use the Shifts option to specify the set of all vectors from the integer lattice so that is a portion of the boundary. We may neglect single point intersections such as .

Our technique essentially works, but the boundary is still not very well approximated. In the next section, we outline a technique to generate very high quality images, which works quite well with this example.

Polygonal Initiators

Many of the examples we have seen are tiles which are topological disks. When this is the case, we might try to approximate the boundary with a polygon and feed this result to the ShowIFS command. Let us illustrate this technique using the stretched tile of the previous section. We choose to work with this tile for three reasons: the previous techniques proved unsatisfactory; the structure of the tile makes it easy to set up the polygonal approximation; and it is an important theoretical example. We start by taking another look at the boundary.

Once again, we are warned that there might be problems. But notice that the defining points in the boundary have been generated. If we can get them in the correct order, we could simply pass a line through them to generate the boundary. Here is one way to do this. We first grab the points corresponding to the left half of the boundary, and then sort them according to the coordinate. The other half of the boundary is simply a reverse-order translate.

Now let us feed the result to the ShowIFS command to see how the set decomposes.

This technique can be extended to many of the other tiles we have looked at in this article. For example, this is how Figure 1 was generated. Unfortunately, most situations require a careful refinement of the digraph IFS algorithms themselves, which is outside the scope of this paper. Furthermore, there is no way to expect that the technique could work in general, since not all self-affine tiles are even connected. Our final example illustrates exactly this point.

Additional Material

McClure.zip

Available at content.wolfram.com/sites/19/2009/01/McClure.zip.

References

[1]	B. Grünbaum and G. C. Shephard, Tilings and Patterns, New York: W. H. Freeman & Co., 1986.
[2]	M. F. Barnsley, Fractals Everywhere, 2nd ed., San Francisco, CA: Morgan Kaufmann Pubs, 2000.
[3]	K. J. Falconer, Fractal Geometry: Mathematical Foundations and Applications, West Sussex, England: John Wiley & Sons Ltd, 1990.
[4]	J. M. Gutiérrez, A. Iglesias, M. A. Rodriguez, and V. J. Rodriguez, “Generating and Rendering Fractal Images,” The Mathematica Journal, 7(1), 1997 pp. 6-13.
[5]	S. Wagon, Mathematica in Action, 2nd ed., New York: Springer-Verlag, 1999.
[6]	C. Bandt, “Self-Similar Sets 5. Integer Matrices and Fractal Tilings of ,” Proceedings of the American Mathematical Society, 112(2), 1991 pp. 549-562.
[7]	R. Darst, J. Palagallo, and T. Price, “Fractal Tilings in the Plane,” Mathematics Magazine, 71(1), 1998 pp. 12-23.
[8]	W. J. Gilbert, “Fractal Geometry Derived from Complex Bases,” The Mathematical Intelligencer, 4(2), 1982 pp. 78-86.
[9]	M. McClure, “Directed-Graph Iterated Function Systems,” Mathematica in Education and Research, 9(2), 2000 pp. 15-26.
[10]	R. S. Strichartz and Y. Wang, “Geometry of Self-Affine Tiles I,” Indiana University Mathematics Journal, 7(1), 1999 pp. 1-23.
[11]	J. C. Lagarias and Y. Wang, “Integral Self-Affine Tiles in I: Standard and Nonstandard Digit Sets,” Journal of the London Mathematical Society, 54(2), 1996 pp. 161-179.
[12]	J. C. Lagarias and Y. Wang, “Integral Self-Affine Tiles in II: Lattice Tilings,” The Journal of Fourier Analysis and Applications, 3, 1997 pp. 84-102.
M. McClure, “Generating Self-Affine Tiles and Their Boundaries,” The Mathematica Journal, 2011. dx.doi.org/doi:10.3888/tmj.11.1-1.

About the Author

Mark McClure, associate professor of mathematics at the University of North Carolina at Asheville, was introduced to Mathematica in 1990 while teaching in the Calculus&Mathematica program as a graduate student at Ohio State University. His primary research is in fractal geometry, particularly as it arises in real analysis. The Mathematical Graphics column grew out of his desire to make high-level mathematics accessible via the use of computer graphics. In addition to mathematics, he enjoys hiking and biking in the mountains of western North Carolina.