Introduction

A periodic tiling is a subdivision of a plane or a higher-dimensional space into closed bounded regions called tiles without holes in such a way that the whole configuration can be reproduced from a finite assembly of tiles by repeatedly shifting and copying in as many directions as needed (c.f. [GS87]).

For the purpose of classification, mathematicians have invented a variety of symbolic descriptions for periodic tilings [Hee68,DDŠ80,GS79,GS81]. Likewise, computer scientist have developed data structures and programs for storing and manipulating tilings [Cho80]. Most of these, however, have been restricted to a rather limited range of applications.

The invention of Delaney symbols has not only provided a mathematical tool for a much more systematic way of studying the combinatorial structure of tilings, thus initiating what we call combinatorial tiling theory (cf. [Dre84,Dre87,DH87,Bal90,Hus93,MP94,MPS97,BM98,DH98,DDH$^+$99,Del00]). Delaney symbols also form the basis for concise and efficient data structures and algorithms in what might be called computational tiling theory.

This article is the first in a projected series of four publications on algorithmic aspects of Delaney symbol theory. I will shortly review the mathematical concept of Delaney symbols and present and analyze some basic algorithms. In forthcoming articles, I will address the relationship between Delaney symbols and tilings in more detail and present methods for enumerating tilings.

As a teaser, please look at the two tilings shown in Figure 1, which were brought to the attention of our group by L. Collatz. They seem to be very similar in their combinatorial structure, but are they actually combinatorially equivalent, i.e., can the first be deformed into the second without breaking symmetries? This is very hard to solve without the proper tools, but becomes very easy with Delaney symbols.

Figure 1: Are these tilings equivalent?

    

Hosted by: