13
$\begingroup$

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!

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 ). $\endgroup$ – Erel Segal-Halevi Nov 2 '13 at 21:02
10
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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