IJPAM: Volume 13, No. 4 (2004)

ON TILABLE ORTHOGONAL POLYGONS

György Csizmadia, Jurek Czyzowicz, Leszek Gasieniec,
Evangelos Kranakis, Eduardo Rivera-Campo, Jorge Urrutia
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
Département d'Informatique
Université du Québec à Hull
e-mail: czyzowicz@uqah.uquebec.ca
Department of Computer Science
University of Liverpool
Peach Street, L69 7ZF, Liverpool, UK
email: leszek@csc.liv.ac.uk
School of Computer Science
Carleton University
e-mail: kranakis@scs.carleton.ca
Departamento di Matematicas
MEXICO
e-mail: erc@xanum.uam.mx
University of Ottawa
School of Information Technology and Engineering
e-mail: jorge@site.uottawa.ca

Abstract.We consider rectangular tilings of orthogonal polygons with vertices located at integer lattice points. Let be a set of reals closed under the usual addition operation. A -rectangle is a rectangle at least one of whose sides is in . We show that if an orthogonal polygon without holes can be tiled with -rectangles then one of the sides of the polygon must be in . 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 dimensions.

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