McGill University - School of Computer Science

Algorithms Seminar

Everybody is welcome.

DATE: Tuesday, January 4
TIME: 4:30 PM - 5:30 PM
PLACE: McConnell 320
TITLE: Generating Aperiodic Tilings Using Quasicrystals
SPEAKER: Mark Grundland, McGill University
   


How can you construct a mosaic of tiles, where each fragment is repeated infinitely many times and yet no single fragment is sufficient to determine the structure of the whole mosaic? In mathematical crystallography, such aperiodic tilings are studied in the theory of quasicrystals. Regular crystals are defined by translational symmetry, whereas the self-similar structure of quasicrystals is characterized by inflational symmetry. The development of the theory of quasicrystals ensued from a revolution in solid state physics, due to the 1984 discovery of metallic alloys which exhibited a long-range atomic order with five-fold rotational symmetry, a structure that is fundamentally incompatible with periodic tilings, which forced a reconsideration of the definition of a crystal.

An aperiodic tiling can be generated by the Voronoi diagram of an aperiodic Delone point set. Such point sets may be constructed using the cut and project method, where a 2N dimensional periodic lattice is projected onto an N dimensional plane which is irrationally oriented with respect to the lattice. Hence, the coordinates of these quasicrystal points need to involve only integers and an irrational number, typically the Golden Ratio. It turns out that these N dimensional quasicrystals may be studied as lattices of one-dimensional quasicrystals since the points that lie on any straight line through an N dimensional quasicrystal correspond to a one-dimensional quasicrystal. Typically, a one-dimensional quasicrystal is composed of only three distinct tiles. Hence, it is easy to generate quasicrystal points using an iterative numerical algorithm. However, a more robust alternative is to exploit the self-similar structure of a quasicrystal, viewing it as the fixed point of a set of substitution rules that act recursively on a finite alphabet of possible tile arrangements. Finally, in order to efficiently render quasicrystals on a computer screen, instead of calculating an exact Voronoi diagram, it is possible to use a discrete Voronoi diagram since there is a minimum distance between any two quasicrystal points.

This seminar, based on the research of Prof. Jiri Patera and his group at Centre de Recherches Mathematiques, will present the mathematical basis for these methods along with a view towards possible applications in computer science, ranging from random number generators to texture synthesis.