Tiling a polygon with two kinds of rectangles - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2002

Tiling a polygon with two kinds of rectangles

(1) , (1)
1

Résumé

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)
Fichier principal
Vignette du fichier
RR2002-46.pdf (192.2 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101939 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101939 , version 1

Citer

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⟩
18 Consultations
363 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More