Computational Aspects of M.C. Escher's Ribbon Patterns

摘要

At the heart of the ideas of the work of Dutch graphic artist M.C. Escher is the idea of automation; we consider a problem that was inspired by some of his earlier and lesser known work. Specifically, a motif fragment is a connected region contained in a closed unit square. Consider a union of motif fragments and call the result an Escher tile T. One can then construct a pattern in the Euclidean plane, as Escher did, with the set of horizontal and vertical unit length translations of T. The resulting pattern gives rise to infinitely many sets of motif fragments (each set may be finite or infinite) that are related visually by way of the interconnections across boundaries of the unit squares that underly the construction; a set of related motif fragments sometimes gives the appearance of a ribbon and thus the resulting pattern in the plane is called a ribbon pattern. Escher's designs gave rise to beautiful artwork and inspired equally aesthetic combinatorial questions as well. In his sketchbooks, Escher coloured the ribbon patterns with pleasing results. Colouring the ribbon patterns led naturally to a question of periodicity: is there a prototile that generates a well-coloured pattern? The current work answers the question in the affirmative by way of tools from graph theory, algorithms, and number theory. We end with tools to help address questions of optimization and a list of open questions.