3
$\begingroup$

This question is motivated by an older question about tiling an orthogonal polygon with squares.

enter image description here         enter image description here

Given a $3\times 2$ rectangle like the first image, the second image is a square partition of that rectangle.

  • A square partitioning is a covering by non-overlapping squares; the entire rectangle must be covered, all the squares must be disjoint.
  • A minimum square partitioning is a square partitioning, for which is no square partitioning that is made of a lesser number of squares.

How can we prove that the second image is a minimum square partitioning of the $3\times 2$ rectangle?

Can we generalize this to ${\rm M{\small IN}S{\small QUARES}}(R_{w,h=w-1})=w$? (see followup question )

$\endgroup$
3
$\begingroup$

The case $w = 3$ is somewhat boring. Here is how to show that you need at least three squares. There is some square $S_1$ touching the bottom-left corner. There is some square $S_2$ touching the bottom-right corner. These squares must be different. At least one of them doesn't go all the way to the top, and so one of the other two corners remains uncovered, requiring another square.

I'm not sure how to extend this proof beyond $w > 3$. Let me just mention that a classical result of Dehn shows that if an $h \times w$ rectangle can be tiled by squares then $h/w$ is rational, and moreover there is some integer $c$ such that if you scale everything by $c$ then all squares have integer sides.

$\endgroup$
  • $\begingroup$ Oh that 2nd paragraph is awesome Yuval. I have a followup, for which I was going to ask about to prove that a {min,any} square-partioning of a integer-placed orthogonal polygon is {integer-placed,rational}. I was going to ask this about a rectangle first since a rectangle is weaker. You've preempted my followup :(. $\endgroup$ – Realz Slaw Nov 8 '13 at 2:51

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.