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

Cited literature [10 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101935
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:10:11 AM
Last modification on : Friday, May 17, 2019 - 1:39:18 AM

File

RR2003-04.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101935, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

5

Files downloads

8