IJPAM: Volume 13, No. 4 (2004)

ON TILABLE ORTHOGONAL POLYGONS

György Csizmadia$^1$, Jurek Czyzowicz$^2$, Leszek Gasieniec$^3$,
Evangelos Kranakis$^4$, Eduardo Rivera-Campo$^5$, Jorge Urrutia$^6$
$^1$Mathematical Institute of the Hungarian Academy of Sciences
P.O. Box 127, 1364 Budapest, HUNGARY
and
SUNY at Brooklyn
Brooklyn, NY 11203, USA
e-mail: csiz@cims.nyu.edu
$^2$Département d'Informatique
Université du Québec à Hull
Hull, Québec J8X 3X7, CANADA
e-mail: czyzowicz@uqah.uquebec.ca
$^3$Department of Computer Science
University of Liverpool
Peach Street, L69 7ZF, Liverpool, UK
email: leszek@csc.liv.ac.uk
$^4$School of Computer Science
Carleton University
Ottawa, ON, K1S 5B6, CANADA
e-mail: kranakis@scs.carleton.ca
$^5$Departamento di Matematicas
Universiad Autonoma Metropolitana-Iztapalapa
MEXICO
e-mail: erc@xanum.uam.mx
$^6$University of Ottawa
School of Information Technology and Engineering
Ottawa, ON, K1N 9B4, CANADA
e-mail: jorge@site.uottawa.ca


Abstract.We consider rectangular tilings of orthogonal polygons with vertices located at integer lattice points. Let $G$ be a set of reals closed under the usual addition operation. A $G$-rectangle is a rectangle at least one of whose sides is in $G$. We show that if an orthogonal polygon without holes can be tiled with $G$-rectangles then one of the sides of the polygon must be in $G$. As a special case this solves the conjecture that domino tilable orthogonal polygons must have at least one side of even length. We also explore separately the case of othogonal polygons placed in a chessboard. We establish a condition which determines the number of black minus white squares of the chessboard occupied by the polygon. This number depends exclusively on the parity sequence of the lengths of the sides of the orthogonal polygon. This approach produces a different proof of the conjecture of the non domino-tilability of of orthogonal polygons without even length sides. We also give some generalizations for polygons with holes and polytopes in $3$ dimensions.

Received: February 1, 2004

AMS Subject Classification: 68R10, 68U05

Key Words and Phrases: domino tilings, odd lengths, orthogonal polygons

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2004
Volume: 13
Issue: 4