Another subdivision tiling can be formed by tiles of two types: equilateral triangles, and 30-30-120 isosceles triangles. The equilateral triangle can be subdivided into three congruent isosceles triangles by connecting each vertex to the center of the triangle. And the isosceles triangle can be subdivided into two similar isosceles triangles and an equilateral triangle, all three having the same area, by trisecting its hypotenuse and connecting the resulting points to the opposite vertex. The following image shows several levels of this subdivision process, with the triangles at each level scaled to have the same area.
Repeating this subdivision and scaling process produces an infinite tiling of the plane (or actually a family of different tilings) which I call the "labyrinth tilings" for reasons to be made clear below.
At first glance, this tiling looks quite uniform: it is formed by a regular pattern of 60-120 rhombuses, each subdivided by a diagonal into two triangles. The only variation occurs in the choice of which diagonal to use. Nevertheless we will see that this tiling has quite an interesting aperiodic structure.
Note that from any step k in the subdivision process that forms the tiling, there is only one way of reversing the process and recovering the tiling at step k-1. For, any equilateral triangle at step k must have exactly two isosceles neighbors (and one equilateral neighbor); this equilateral triangle and pair of isosceles neighbors forms a larger isosceles triangle at step k-1. The remaining isosceles triangles form triples meeting at their obtuse angles, which form larger equilateral triangles at step k-1. From the triangles at step k-1 we can recover those at step k-2, and so on.
Define the position code of each triangle in a labyrinth tiling to be the infinite sequence of shapes and orientations of these larger and larger triangles at previous levels of the subdivision.
The position code of a single triangle determines the arrangement of triangles in all neighborhoods of the triangle, and therefore determines the overall labyrinth tiling. Two triangles belong to the same tiling when their position codes differ in only a finite number of places. (There are also some cases when two points separated by an infinite ray of a tiling can have position codes differing in infinitely many places.)
The existence of these position codes shows that any labyrinth tiling is aperiodic. For, any point in the triangle belongs to a unique triangle at any previous level j<k of the subdivision process. In particular we can choose j so that the triangle is larger than any given period of translational symmetry. No point within this large triangle can be taken to any other point in the triangle by a translational symmetry. So no such symmetry can exist, and the tiling is aperiodic. (Note that, just as in the case of the Penrose tilings, a finite number of rotational symmetries may still exist).
These edges seem to mark out the boundaries of a space-filling labyrinth that covers the entire plane. (The labyrinths of the ancients, unlike modern mazes, were typically unicursal, having neither branches nor dead ends [Phillips].) Because of the tiling's six-fold symmetry, this labyrinth is overlaid with two others, at 30 and 60 degree angles to it.
These patterns can be explained using position codes. It turns out that, given any two points in the tiling, either an infinite horizontal or vertical ray in the tiling crosses the line segment between them, or there is a unique sequence of triangles that forms a path connecting them and is not crossed by any horizontal or vertical edges.
To prove this, look at the position codes of the two points. Eventually the large triangles in the codes get so large that there is only room for two possible configurations: either the two points are in a single large triangle, or they are in two adjacent triangles.
If the two points are in adjacent triangles at all the infinitely many levels of the position codes, and if those triangles are always separated by a horizontal or vertical segment, then these segments combine to form an infinite horizontal or vertical ray or line. In this case, this line may separate the points from each other.
Otherwise, at some level j of the subdivision process, the path we are looking for connecting the two points consists simply of these one or two triangles from the position codes of the two points. We now show that each level of the subdivision process preserves the existence of these paths. To do this, we use a slightly modified version of the subdivision process that ends up tiling a larger area than the original triangles. At each step, we follow the usual subdivisions described above, except that if the resulting area has an isosceles triangle hypotenuse on its boundary that is neither vertical nor horizontal, we add the matching triangle on the other side of that edge. Because of this addition, all isosceles triangles with slanted hypotenuses can be assumed to form matched pairs.
As can be seen above, if before the subdivision a set of triangles is crossed by a path of triangles (connected to each other by slanted edges), a modified version of the same path will wind through the same region after the subdivision. Therefore there is a single path covering a region surrounding the two given points, which produces the unique path connecting the points that I claimed existed.
From the Geometry Junkyard,
computational
and recreational geometry.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Last update: .