Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
4  
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
4  
Tiling a rectangle with the fewest squares. Kenyon, Richard J. Combin. Theory Ser. A 76 (1996), no. 2, 272–291. ams.org/leavingmsn?url=http://dx.doi.org/10.1006/jcta.1996.0104 "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
3  
Also see. Rectangles as sums of squares. Walters, Mark Discrete Math. 309 (2009), no. 9, 2913–2921.ams.org/leavingmsn?url=http://dx.doi.org/10.1016/… 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
1  
See also the question mathoverflow.net/q/116382/7252 which refers to this one. –  András Salamon Sep 26 '13 at 15:29
show 1 more comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.