Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Small An optimal algorithm to generate tilings.

Abstract : A lot of progress has been made in tiling theory in the last ten years after Thurston (\cite{Thu90}), building on previous work by Conway and Lagarias (\cite{CL90}), introduced height functions as a tool to encode and study tilings. This allowed the authors of this paper, in previous work (\cite{Rem99}, \cite{Des01}), to prove that the set of lozenge (or domino) tilings of a hole-free, general-shape domain in the plane can be endowed with a distributive lattice structure. In this paper, we see that this structure allows us in turn to construct an algorithm that is optimal with respect to both space and execution time to generate all the tilings of a domain~$D$. We first recall some results about tilings and then we describe the algorithm.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:10:11 AM
Last modification on : Wednesday, October 26, 2022 - 8:15:17 AM


Files produced by the author(s)


  • HAL Id : hal-02101935, version 1



Sébastien Desreux, Eric Rémila. Small An optimal algorithm to generate tilings.. [Research Report] LIP RR-2003-04, Laboratoire de l'informatique du parallélisme. 2003, 2+12p. ⟨hal-02101935⟩



Record views


Files downloads