Skip to Main content Skip to Navigation

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

Cited literature [16 references]  Display  Hide  Download
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:10:16 AM
Last modification on : Saturday, September 11, 2021 - 3:18:55 AM


Files produced by the author(s)


  • HAL Id : hal-02101939, version 1



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⟩



Les métriques sont temporairement indisponibles