Tiling a Polygon with Two Kinds of Rectangles |
| |
Authors: | Eric Rémila |
| |
Institution: | (1) Laboratoire de l’Informatique du Parallelisme, UMR 5668 CNRS-INRIA-ENS Lyon-Universite Lyon 1, 46 allee d’Italie, 69364 Lyon Cedex 07 and Groupe de Recherche en Informatique et Mathematiques Appliquees, IUT Roanne (Universite St-Etienne), 20 avenue de Paris, 42334 Roanne Cedex, France |
| |
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 Conway’s tiling groups and extends the results of Kenyon and Kenyon (limited to the
case when each rectangle has a side of length 1). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|