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.

Hosted by:

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