An optimal algorithm to generate tilings (Q2466003)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An optimal algorithm to generate tilings |
scientific article |
Statements
An optimal algorithm to generate tilings (English)
0 references
11 January 2008
0 references
The authors study tilings of finite simply connected regions of the square or triangular lattice with dominoes (\(2\times 1\) rectangles) or lozenges (consisting of two equilateral triangles of unit size sharing a whole side), respectively. They describe an algorithm that is optimal with respect to both space and execution time to generate all domino or lozenge tilings of a given region. An essential tool is the height function which associates to each vertex of a tiling an integer in such a way that it encodes the tiling uniquely. The height function is then used to further encode a tiling by a word, and the algorithm produces to each such word the successor with respect to the lexicographical order, starting with the minimal tiling which is constructed by an algorithm due to \textit{W. P. Thurston} [Am. Math. Mon. 97, 757--773 (1990; Zbl 0714.52007)].
0 references
tiling
0 references
lozenge tiling
0 references
domino tiling
0 references
height function
0 references
0 references