# 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.
Keywords :
Document type :
Reports
Domain :

Cited literature [10 references]

https://hal-lara.archives-ouvertes.fr/hal-02101935
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:10:11 AM
Last modification on : Saturday, September 11, 2021 - 3:18:55 AM

### File

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

### Identifiers

• HAL Id : hal-02101935, version 1

### 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⟩

### Metrics

Les métriques sont temporairement indisponibles