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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references