Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431385 | Journal of Discrete Algorithms | 2006 | 13 Pages |
Abstract
We produce an algorithm that is optimal with respect to both space and execution time to generate all the lozenge (or domino) tilings of a hole-free, general-shape domain given as input.We first recall some useful results, namely the distributive lattice structure of the space of tilings and Thurston's algorithm for constructing a particular tiling. We then describe our algorithm and study its complexity.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sébastien Desreux, Eric Rémila,