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 :
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:10:11 AM
Last modification on : Wednesday, November 20, 2019 - 2:52:28 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