Open Collections

Computational aspects of Escher tilings

University of British Columbia

At the heart of the ideas of the work of Dutch graphic artist M.C. Escher is the idea of automation. We consider one such problem that was inspired by some of his earlier and lesser known work [MWS96, Sc90, Sc97, Er76, Es86]. From a finite set of (possibly overlapping) connected regions within a unit square (Figure 1), is it possible to make a prototile with concatenated and colored copies of the original square tile (Figure 2), such that the pattern in the plane arising from tiling with the prototile • uniformly colors connected components, and • distinctly colors overlapping components (Figure 3)? The answer is yes, that such a prototile exists for any (suitably defined) design confined to a unit square. We present a proof of existence and an efficient (and implementable) algorithm to construct prototiles. Moreover, in the existence proof, it will become apparent that a prototile for a given design may not be unique (up to concatenation). In such a situation, there are infinitely many "measurably different" prototiles. The secret of each design is encoded by either one or infinitely many (number theoretic) lattices; we will show how to extract all possible lattices by using techniques from graph theory and graph algorithms. Finally, from a certain point of view, the prototiles that we construct are canonical. We begin an analysis of the canonical prototiles by making a connection from lattices to binary quadratic forms to class number.

Thesis/Dissertation

application/pdf

2009-09-22

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/12987

Computer Science

University of British Columbia

UBCV

DSpace