next up previous
Next: Algorithms Up: Data structures and algorithms Previous: Introduction

Delaney symbols

After introducing Delaney symbols by describing their construction for a two-dimensional tiling, I will give a general characterization and review some of the most important mathematical results.

Please note that in the following, the edges and vertices of a tiling will be defined in a purely combinatorial way. Thus, in Dimension 2, a vertex is a point where at least three tiles meet. An edge is a portion of the common boundary of two tiles in between two vertices.

Figure 2: An archimedean tiling
\includegraphics[width=0.4\textwidth]{tiling}

Consider the tiling shown in Figure 2. First, a barycentric subdivision is constructed as follows:

Ideally, the barycentric subdivision should be constructed as to retain the symmetry of the tiling. This is always possible. A closeup of Figure 2 together with its barycentric subdivision is shown in Figure 3.

Figure 3: Constructing the barycentric subdivision
\includegraphics[width=0.3\textwidth]{closeup}     \includegraphics[width=0.3\textwidth]{barycentric}

Obviously, the barycentric subdivision is a triangulation. To avoid confusion, we will refer to its tiles as chambers. Each chamber has three types of vertices, namely one being an original vertex, one chosen inside an edge and one chosen inside a tile. We label these `0', `1' and `2', accordingly. There are also three types of edges. Edges are labelled the same as the vertices opposite to them. In Figure 3, edges labelled `0' are shown dashed, those labelled `1' are shown dotted, while edges labelled `2' are shown solid.

Each chamber has three neighbors, which are distinguished by the type of edge they share with it. Thus, any finite portion of the triangulation can be described completely by listing for each chamber its three neighbors in order. For a given chamber t, we will denote these by s0(t), s1(t) and s2(t), respectively.

Figure 4: Symmetry equivalence classes of chambers.
\includegraphics[width=0.5\textwidth]{classes}

Next, we take symmetries into account. Two chambers are called symmetry equivalent if there is a symmetry of the tiling mapping one onto the other. In Figure 4, equivalent chambers are marked with a common letter. Clearly, there are 10 classes in this particular case, which bear the letters `A' up to `J'.

As corresponding neighbors of chambers in the same class belong to the same class again, we can assign to each class C its three ``neighboring'' classes s0(C), s1(C) and s2(C), respectively, where the class si(C) consist of all the neighbors si(t) of chambers t in class C. The set of classes together with its neighborhood relations is called the Delaney set1. It is convenient to envision the classes as nodes and the neighborhood relations as labelled edges of a graph. Consequently, the term Delaney graph is used as well. Note that the edges of the Delaney graph are undirected, because the neighborhood relations are reflective. Of course, the set of chambers of the barycentric subdivision can be regarded as a -- possibly infinite -- graph in the same way, which we will call the chamber graph.

It is always possible to choose a connected region containing one chamber of each type, as shown in gray in Figure 4. Such a region forms a particular fundamental domain for the tiling's symmetry group. A convenient way to explore the Delaney graph is to extract a fundamental domain together with its immedatiately surrounding chambers, as depicted in Figure 5.

Figure 5: A fundamental domain.
\includegraphics[width=0.3\textwidth]{fdomain}

Clearly, the Delaney graph alone does not uniquely determine the tiling. This becomes obvious when we consider the archimedean solid, or spherical tiling, depicted in Figure 6, which has exactly the same Delaney graph as our plane example, but contains squares instead of regular hexagons.

Figure 6: An archimedean solid.
\includegraphics[width=0.35\textwidth]{archimedean}

We augment the Delaney graph by assigning to each class C of chambers the two numbers m0(C) and m1(C). The first of these gives the degree, i.e., the number of vertices, of the faces containing chambers of this class, while the second gives the degree of the vertices adjacent to chambers of this class. By construction, neither of these numbers depends on the actual chamber chosen, so they are ``well-defined''. The augmented Delaney graph is called the Delaney symbol of the tiling in question. The Delaney symbol for the tiling in Figure 2 is shown in tabular form and as a labelled graph in Figure 7. The Delaney symbol for the archimedean solid of Figure 6, as a matter of fact, can be obtained by setting both m0(A) and m0(B) to 4 instead of 6.

Figure 7: The Delaney symbol.
class s0 s1 s2 m0 m1
A B B C 6 5
B A A D 6 5
C D H A 3 5
D C E B 3 5
E F D I 3 5
F E G J 3 5
G H F H 3 5
H G C G 3 5
I J J E 3 5
J I I F 3 5
     \includegraphics[width=0.5\textwidth]{dsymbol}

Delaney symbols are insensitive to deformations of tilings as long as these change neither the topology nor the symmetries. More precisely, two tilings are said to be topologically equivalent if there is a homeomorphism -- a both-ways continuous transformation -- mapping tiles of the first onto tiles of the second. It is said to be combinatorially equivalent if there is such a transformation which in addition maps (by conjugation) the symmetry group of the first to the symmetry group of the second. By construction, Delaney symbols are invariants of combinatorial equivalence classes. The first and most important theorem reviewed here states that they are even sharp invariants.

Theorem 1 ([Dre84])   Two tilings are combinatorially equivalent if and only if their respective Delaney symbols are isomorphic.

Two Delaney symbols are isomorphic if one can be obtained from the other just by renaming the nodes. This can be efficiently tested, as will be demonstrated below.

Theorem 1 remains true in higher dimensions, where the construction of the Delaney symbol is performed in an analoguous way. In fact, it holds true whenever both spaces tiled are simply connected manifolds. A manifold is anything that locally looks like an ordinary euclidean space, whereas a space is simply connected if every closed curve in it can be continuously deformed into a single point without leaving the space. An example of a manifold which is not simply connected is the surface of a doughnut, also called a torus.

Following is a characterization of ``formal'' Delaney symbols in arbitrary dimension, using those properties which are immediate from the construction.

Definition 2   A Delaney symbol of dimension n is a set C together with functions s0,..., sn from C into C and functions m0,..., mn - 1 from C into the positive integers, such that the following is true for all C $ \in$ C and all applicable i and j:

(DS0)
The underlying Delaney graph is connected, i.e., each element can be mapped onto any other by repeatedly applying functions from the set s0,..., sn.

(DS1)
si(si(C)) = C.

(DS2)
si(sj(C)) = sj(si(C)) whenever j > i + 1.

(DS3)
mi(C) = mi(si(C)) = mi(si + 1(C)).

(DS4)
fimi(C)(C) = C,
where fi0(C) : = C and fik + 1(C) : = si(si + 1(fik(C))).

For practical reasons, we will usually assume that Delaney symbols are finite. We will therefore restrict our attention to tilings which possess finite Delaney symbols, as periodic tilings do. We will refer to these as generalized periodic tilings. Among the generalized periodic tilings are tilings of spheres and also certain tilings of hyperbolic spaces.

The following notations will be useful:

Definition 3   Let C be an n-dimensional Delaney symbol. For C $ \in$ C and 0 $ \leq$ i < j $ \leq$ n, define ri, j(C) as the smallest positive number r such that fi, jr(C) = C, where fi, j0(C) = C and fi, jk + 1(C) = si(sj(fi, jk(C))). Define vi, j(C) as the fraction mi(C)/ri, j(C) if j = i + 1 and as 2/ri, j(C) otherwise.

Next, we consider how to determine whether a given formal Delaney symbol actually is derived from a tiling of, say, the euclidean plane. In dimension 2, this can be done using a simple numerical invariant:

Definition 4   Let C be a two-dimensional Delaney symbol. The curvature of C is defined as the sum

K(C) : = $\displaystyle \sum_{C\in{\mathbf{C}}}^{}$k(C)

where

k(C) : = $\displaystyle {\frac{1}{m_0(C)}}$ + $\displaystyle {\frac{1}{m_1(C)}}$ - $\displaystyle {\textstyle\frac{1}{2}}$.

Theorem 5   Let C be a two-dimensional Delaney symbol. Then C encodes a tiling of

To illustrate this, for the Delaney symbol in Figure 7, we have

k(A) = k(B) = $\displaystyle {\textstyle\frac{1}{6}}$ + $\displaystyle {\textstyle\frac{1}{5}}$ - $\displaystyle {\textstyle\frac{1}{2}}$ = $\displaystyle {\frac{5+6-15}{30}}$ = $\displaystyle {\frac{-4}{30}}$

and

k(C) = ... = k(J) = $\displaystyle {\textstyle\frac{1}{3}}$ + $\displaystyle {\textstyle\frac{1}{5}}$ - $\displaystyle {\textstyle\frac{1}{2}}$ = $\displaystyle {\frac{10+6-15}{30}}$ = $\displaystyle {\textstyle\frac{1}{30}}$,

thus

K(C) = $\displaystyle {\frac{2\cdot(-4) + 8\cdot 1}{30}}$ = 0,

whereas for the Delaney symbol of the archimedean solid shown in Figure 6, we have

k(A) = k(B) = $\displaystyle {\textstyle\frac{1}{4}}$ + $\displaystyle {\textstyle\frac{1}{5}}$ - $\displaystyle {\textstyle\frac{1}{2}}$ = $\displaystyle {\frac{5+4-10}{20}}$ = $\displaystyle {\frac{-1}{20}}$ = $\displaystyle {\frac{-3}{60}}$,

thus

K(C) = $\displaystyle {\frac{2\cdot(-3) + 8\cdot 2}{60}}$ = $\displaystyle {\textstyle\frac{10}{60}}$ = $\displaystyle {\textstyle\frac{1}{6}}$ > 0.

Moreover, we have 4/K(C) = 24, which implies that vi, j(C) must divide 24 for all applicable C, i and j. This is indeed the case.

Actually, the quantities vi, j(C) and, if the curvature is positive, the number 4/K(C) as well, have important interpretations. The symmetry group of a spherical tiling with Delaney symbol C has exactly 4/K(C) elements. As is obvious from the definitions, a value of vi, j(C) larger than 1 indicates a rotation of that order fixing the vertex -- or, in general, the face of co-dimension 2 -- of any chamber in class C at the intersection of its two co-dimension 1 faces labelled i and j.

The proof of Theorem 5 relies on the Euler characteristic of surfaces. Since the Euler characteristic is always 0 in odd dimensions, no analogous result is available for three-dimensional Delaney symbols. In [Del00], a partial algorithm is described for the recognition of Delaney symbols of three-dimensional tilings.

Every face, i.e., in the two-dimensional case, every vertex, edge and tile, of a tiling is represented by a unique vertex of its barycentric subdivision. This vertex is labelled i if it lies in an i-dimensional face. Two chambers t and t' share a common i-vertex if and only if they lie in the same connected component of the graph obtained by removing all i-edges from the chamber graph. These are exactly those chambers which have a non-empty intersection with the given face. This relationship carries over to the Delaney symbol, where symmetry equivalence classes of i-faces are represented by connected components of the partial Delaney graph obtained by removing all i-edges.

These connected components are an important tool in combinatorial tiling theory, especially in dimensions 3 and higher. Together with the relevant `m'-functions, we refer to them as subsymbols. An I-subsymbol of an n-dimensional Delaney symbol C is defined by an element C $ \in$ C and a subset I $ \subset$ {0,..., n}. It consists of all elements of C which can be reached from C by repeatedly applying only functions si with i $ \in$ I. A {0,..., n - 1}-subsymbol, for example, represents the combinatorial structure of a tile.

The Delaney symbol in Figure 7 contains the three {0, 1}-subsymbols {A, B}, {C, D, E, F, G, H} and {I, J}.

To complete this section, let us consider tilings which are topologically, but not combinatorially equivalent. Figure 8 shows a simple tiling by squares and a topologically equivalent one by rectangles, both with barycentric subdivisions and letters marking respective chamber classes. In the rectangle tiling, the reflections at the diagonals are no longer symmetries of the tiling, so its Delaney symbol has two elements instead of just one in the case of the square tiling.

Figure 8: Two topologically, but not combinatorially equivalent tilings.
\includegraphics[height=1.5in]{square}     \includegraphics[height=1.5in]{rect}

The rectangle tiling is called a symmetry breaking of the square tiling. There is a homeomorphism which maps tiles of the rectangle tiling onto tiles of the square tiling and symmetries of the rectangle tiling to symmetries of the square tiling, but not all symmetries of the square tiling are obtained in this way. Such a homeomorphism also takes chambers and chamber classes of the first tiling onto chambers and chamber classes of the second one, thereby inducing a well-behaved mapping between their Delaney symbols, which we call a Delaney map or just a map.

Definition 6   A function f$ \colon$C$ \to$C$\scriptstyle \prime$ between Delaney symbols C and C$\scriptstyle \prime$ is called a Delaney map if and only if for each C $ \in$ C and for all applicable i: A Delaney map is called an isomorphism if it is one-to-one. A Delaney symbol is called minimal if every Delaney map defined on it is an isomorphism.

Every isomorphism has a reverse map which is a Delaney map, which justifies its name. For finite Delaney symbols, a Delaney map is an isomorphism if both symbols have the same size. A finite Delaney symbol is minimal if it can not be mapped onto a smaller one.

If f$ \colon$C$ \to$C$\scriptstyle \prime$ is a Delaney map and C$\scriptstyle \prime$ is the Delaney symbol of a tiling, then C is the Delaney symbol of a symmetry breaking of that tiling. If C corresponds to some tiling, then a tiling corresponding to C$\scriptstyle \prime$ would have to have more symmetries, which might not always be possible. It has been shown, however, that for all C corresponding to either a two-dimensional or a euclidean three-dimensional tiling, C$\scriptstyle \prime$ will correspond to a tiling of the same geometry [Del00].

As will be shown in the next section, there is for every Delaney symbol a unique minimal image, which can be computed efficiently. This means that, at least for two-dimensional and euclidean three-dimensional tilings, every topological equivalence class has a unique representative with maximal symmetry.


next up previous
Next: Algorithms Up: Data structures and algorithms Previous: Introduction


Hosted by:
SourceForge.net Logo
Author: Olaf Delgado-Friedrichs (odf at users.sourceforge.net)   Date: July 28, 2005