Tiling a polygon with two kinds of rectangles

Olivier Bodini (1) , Eric Remila (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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$).

Nous fixons deux rectangles aux dimensions entières. Nous produisons un algorithme en temps quadratique qui, étant donné un polygone F en entré, donne un pavage de F avec des copies traduites de nos rectangles (ou indique qu’il n’y a pas de pavage). De plus, nous prouvons que toute paire de pavages peut être relié par une suite de transformations locales élémentaires. Cette étude utilise les groupes de pavages de J. H. Conway et étend les résultats de C. Kenyon and R. Kenyon (limités au cas ou chaque rectangle a une dimension unitaire)

Mots clés: Flip; Height Function; Tiling Group; Tiling

Mots clés: Pavage; Groupe de pavage; Fonction de hauteur

Domaines: Informatique [cs]

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⟩