Path: utzoo!mnetor!tmsoft!torsqnt!jarvis.csri.toronto.edu!neat.cs.toronto.edu!lcai
From: lcai@ai.toronto.edu (Cai Leizhen)
Newsgroups: comp.theory
Subject: Square Tiling
Message-ID: <89Nov17.221726est.2426@neat.cs.toronto.edu>
Date: 18 Nov 89 03:18:41 GMT
Distribution: na
Organization: Department of Computer Science, University of Toronto
Lines: 16

I would like to know the complexity of the following problem.

Given a M*N rectangle, find the minimum number of squares required to exactly
cover the rectangle.

Note: No restrcition on sizes of squares. You can cover it use M*N squares,
for example.

Any comments will be appreciated. I guess it may be studied already, but
I could not find any references.

Leizhen Cai
Dept. of Computer Science
Univ. of Toronto
lcai@csri.utoronto.ca