Algorithms Seminar

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 se! t ! 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.