Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was writing up a description of the Euclidean algorithm for a set of course notes and was playing around with one geometric intuition for the algorithm that involves tiling an $m \times n$ rectangle with progressively smaller squares, as seen in this animation linked from the Wikipedia article:

I was looking over this animation and was curious whether or not the squares that you would place down in the course of this algorithm necessarily gave the minimum number of squares necessary to cover the entire rectangle.

More formally: suppose that you are given an $m \times n$ rectangle, where $m, n \in \mathbb{N}$ and $m, n > 0$. Your goal is to tile this rectangle with a set of squares such that no two squares overlap. Given $m$ and $n$, what is the most efficient way to place these tiles?

Is the tiling suggested by the Euclidean algorithm (that is, in an $m \times n$ rectangle, with $m \ge n$, always place an $n \times n$ rectangle, then recurse on the remaining rectangle) always optimal? If not, is there are more efficient algorithm for this problem?

I am reasonably sure that the Euclidean approach is correct, but I was having a lot of trouble formalizing the intuition with a proof due to the fact that there are a lot of different crazy ways you can try to place the squares. For example, I'm not sure how to have the proof handle the possibility that squares could be at angles, or could have side lengths in $\mathbb{R} - \mathbb{Q}$.

Thanks!

share|improve this question
    
Related: math.stackexchange.com/questions/92382/proofs-for-an-equality –  user17762 Jun 25 '12 at 23:11
1  
It's actually pretty straightforward to show that the squares can't be at angles (since any juncture between edges has to be 90 degrees, there are only two possible orientations for lines to be at, and those have to match the two orientations of the rectangle's edges), and it shouldn't be much more complicated to show that all side lengths must be rational (more specifically, side lengths have to be commensurate for any tiling.) –  Steven Stadnicki Jun 25 '12 at 23:14
    
For a start, see Stan Wagon's Fourteen proofs of a result about tiling a rectangle (see his references). –  Bill Dubuque Jun 25 '12 at 23:28
    
1  
@Erel A web search easily locates a fresh link to Wagon's paper. –  Bill Dubuque Dec 15 '13 at 4:19

2 Answers 2

up vote 5 down vote accepted

Euclid doesn't always minimize the number of squares. E.g., with an $8\times9$ rectangle, Euclid says use an 8-square and 8 1-squares, 9 squares in all. But you can do it with a 5, two 4s, a 3, a 2, and two 1s, making 7 squares total. You put the 5 in a corner, then put the 4s in the corners that have room for them; that leaves a $3\times5$ rectangle to fill, which you can do by Euclid.

share|improve this answer
1  
There is a smaller example, with a $5 \times 6$ rectangle. The Euclid algorithm produces a tiling with 6 squares: 1 5-square and 5 1-squares. It is possible to tile the rectangle with 5 squares: 2 3-squares and 3 2-squares (The example is from Fractality: math.stackexchange.com/questions/479192/squaring-rectangles ). –  Erel Segal Halevi Nov 2 '13 at 21:02

Recalling Kenyon's work on this, I found these comments in an old MO post

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+C \log p$ squares of integer size, for some universal constant $C.$''

Rectangles as sums of squares. Walters, Mark Discrete Math. 309 (2009), no. 9, 2913–2921. 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 2010 at 9:18

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.