Abstract | ||
---|---|---|
We first prove that the set of domino tilings of a fixed finite figure is a distributive lattice, even in the case when the figure has holes. We then give a geometrical interpretation of the order given by this lattice, using (not necessarily local) transformations called flips.This study allows us to formulate an exhaustive generation algorithm and a uniform random sampling algorithm.We finally extend these results to other types of tilings (calisson tilings, tilings with bicolored Wang tiles). |
Year | DOI | Venue |
---|---|---|
2004 | 10.1016/j.tcs.2004.02.020 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
calisson tilings,distributive lattice,Tiling,lattice,Height function,exhaustive generation algorithm,fixed finite figure,uniform random sampling algorithm,bicolored Wang tile,related model,tiling,geometrical interpretation,height function,Lattice,domino tilings | Journal | 319 |
Issue | ISSN | Citations |
1-3 | Theoretical Computer Science | 3 |
PageRank | References | Authors |
0.56 | 11 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sébastien Desreux | 1 | 9 | 1.78 |
Martin Matamala | 2 | 38 | 3.69 |
Ivan Rapaport | 3 | 199 | 21.93 |
Eric Rémila | 4 | 329 | 45.22 |