Tiling a polygon with two kinds of rectangles

Abstract : We fix two rectangles with integer dimensions. We give a quadratic time algorithm which, given a polygon F as input, produces a tiling of F with translated copies of our rectangles (or indicates that there is no tiling). Moreover, we prove that any pair of tilings can be linked by a sequence of local transformations of tilings, called flips. This study is based on the use of J. H. Conway's tiling groups and extends the results of C. Kenyon and R. Kenyon (limited to the case when each rectangle has a side of length $1$).
Document type :
Reports
Complete list of metadatas

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

File

RR2002-46.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101939, version 1

Collections

Citation

Olivier Bodini, Eric Remila. Tiling a polygon with two kinds of rectangles. [Research Report] LIP RR-2002-46, Laboratoire de l'informatique du parallélisme. 2002, 2+15p. ⟨hal-02101939⟩

Share

Metrics

Record views

6

Files downloads

32