MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes). Is there an efficient way to calculate this?

share|cite|improve this question
Euclidean algorithm gives an upper bound quickly: for m < n, something like O(n/m + log m + m/gcd(n,m)). Gerhard "Ask Me About System Design" Paseman, 2010.11.02 – Gerhard Paseman Nov 2 '10 at 7:46
I can give an even quicker upper bound..$mn$. I guess a $5 \times 6$ rectangle shows that the greedy/Euclidean strategy does not always give the minimum. – Aaron Meyerowitz Nov 2 '10 at 7:49
Tiling a rectangle with the fewest squares. Kenyon, Richard J. Combin. Theory Ser. A 76 (1996), no. 2, 272–291. "We show that a square-tiling of a p×q rectangle, where p and q are relatively prime integers, has at least log 2p squares. If q>p we construct a square-tiling with less than q/p+Clogp squares of integer size, for some universal constant C.'' – Vagabond Nov 2 '10 at 9:03
Also see. Rectangles as sums of squares. Walters, Mark Discrete Math. 309 (2009), no. 9, 2913–… Where precisely this question is discussed and is ascribed to Laczkovich (i.e., the minimum number of squares needed to tile an integer sided rectangle ( the squares are not assumed to be integer sided though)). Of course you are asking for an efficient algorithm which is a different question ... Kenyon paper does discuss some algorithm(greedy) though. – Vagabond Nov 2 '10 at 9:18
See also the question which refers to this one. – András Salamon Sep 26 '13 at 15:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.