Back to search

University of British Columbia

Computational aspects of Escher tilings

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2002

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gethner, Ellen

Rights

dc:rights
Statement dc:rights
  • 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.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/12987

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Gethner, Ellen. Computational aspects of Escher tilings. doctoral thesis, University of British Columbia, 2002. http://hdl.handle.net/2429/12987