Generally, a tesselation (sometimes called a tiling or mosaic) is a division of space into pieces with finite area (or volume) called tiles. Tesselations and patterns have been in art for at least two thousand years. Ancient artifacts decorated with repeating patterns, tiled buildings like the Alhambra, and mosaics on the frames of artwork are all evidence of the widespread and age-old use of tesselations. Tesselations in nature include the bee's honeycomb, atomic structures of crystals, cell arrangements in life forms, patches of dried up mud and the design of spider's web. The manufacture of components, by stamping them out of sheets of metal, is made efficient by minimizing the unused portion of the metal. Thus tiling has applications to industry. Also communication theorists use "random tesselations" for image enhancement and coding. Crystallography uses tesselations of three-dimensional space to understand the structures of molecules.
The mathematical theory of tesselations, however, is less than a century old. In mathematics, tesselation usually means a plane-filling arrangement of polygons such that the intersection of any two of the polygons is empty, a point, or a line segment. This definition easily generalizes to higher dimensions. For example, the standard grid is a tiling by squares and the cubic lattice is a tiling by cubes. An isometry is a map, f say, from Euclidean space to itself that preserves distances, i.e. for any points x any y, |x-y| = |f(x) - f(y)|. If an isometry maps the tiling to itself (i.e. if x is a corner point of a tile then so is f(x) and vice versa), then it is called a symmetry of the tiling. The set of all such symmetries is called the symmetry group. For example, the symmetry group of the standard tiling by 1x1 squares is equal to the set of all compositions of the following two maps and their inverses: the map that takes any arbitrary point (x, y) to (x + 1,y) and the map that takes (x, y) to (x, y + 1). A fundamental domain for the tiling is a polygon with the property that its images under the symmetry group form a tiling of the plane. In the standard tiling by squares, any 1x1 square is a fundamental domain. Fedorov (1891) classified the symmetry groups of all two-dimensional and three-dimensional tilings. The crystallographic groups are the symmetry groups for which there is a fundamental domain with finite area (or volume). Fedorov showed that there are 17 two-dimensional crystallographic groups and 230 three-dimensional ones (up to isomorphism). Bieberbach(1911) solved part of the eighteenth problem on Hilbert's list (see Hilbert's problems) when he showed that the number of crystallographic groups up to isomorphism is finite in every dimension. Brown and others proved in 1978 that there are 4783 classes of four-dimensional crystallographic groups. The numbers of crystallographic groups in dimensions five and higher are unknown at this time.
An isohedral tiling is one in which every tile is a fundamental domain. Two-dimensional isohedral tilings have been classified by Grunbaum and Shepherd in their famous book Tilings and Patterns (1987). This book is the most comprehensive work on mathematical tilings to date. Polygons that can tile the plane isohedrally were classified by Reinhardt in 1918. If the tiles of a tiling are all congruent to each other, then the tiling is said to be monohedral. Polygons that can tile the plane monohedrally are far from classified. For example, it is not known which convex pentagons can tile the plane monohedrally although fourteen types have been discovered. It is not even known whether or not there an algorithm exists that can determine whether a polygon can tile the plane monohedrally. One attempt at finding such an algorithm is the following. The Heesch number of the polygon is the maximum number of times the polygon can be surrounded by copies of itself. If the polygon can tile the plane then its Heesch number is infinity. Polygons with Heesch number 0,1,2, 3, 4 and 5 have been found. It is unknown whether there are polygons with Heesch number greater than 5 but less than infinity. But if there are none, then there is an algorithm to decide whether a polygon can tile the plane - place copies of itself around itself to see if it has at least six coronas such that each completely surrounds the previous corona.
In 1966 Robert Berger proved that there is no algorithm that can determine whether any arbitrary set of polygons can tile the plane. This does not prove that there is no algorithm for determining whether a single polygon can tile the plane however because Berger used sets of more than one polygon. He found a way for a set of polygons to mimic a Turing machine. He then used the fact that the halting problem for Turing machines is undecidable to prove that it is also undecidable whether or not his tiles can tile the whole plane. He also gave the first example of an aperiodic set of polygons. These are sets of polygons that can tile the plane but only in such a way that the symmetry group of any of their tilings is finite. Berger's aperiodic set consisted of 20,426 polygons. By 1971, Robert Robinson had found a set consisting of only 6 tiles. In 1974, Roger Penrose discovered an aperiodic set of 2 polygons, the so-called Penrose tiles. It's unknown at this time whether there exists an aperiodic set of only one polygon.
There are many areas of current research in tilings of which we have mentioned only a few. For a more complete introduction into tilings, see Grunbaum and Shepherd's book Tilings and Patterns.
This is the complete article, containing 940 words
(approx. 3 pages at 300 words per page).
