patternMinor
What is the minimum square partition of an almost-square rectangle?
Viewed 0 times
partitionthewhatalmostrectangleminimumsquare
Problem
This question is motivated by an older question about tiling an orthogonal polygon with squares.
It is a generalisation of my former question about how to prove that the minimum square partition of a 3X2 rectangle has 3 squares).
Let:
Illustration:
Top row: The almost-square-rectangles of widths $3$, $4$ and $5$. Bottom row: Are these miminum-square-partitions of their corresponding rectangles?
My question is now:
What is the minimum-square-partitioning of an almost-square-rectangle?
Can we prove ${\rm M{\small IN}S{\small QUARES}}(R_{w,h=w-1})=w$?
Note a follow-up question, Minimum square partitions for 4x3 and 5x4 rectangles.
It is a generalisation of my former question about how to prove that the minimum square partition of a 3X2 rectangle has 3 squares).
Let:
- An almost-square-rectangle be a rectangle that has a width $w$ and height $h=w-1$.
- A square partitioning be a covering by non-overlapping squares; the entire rectangle must be covered, all the squares must be disjoint.
- A minimum-square-partitioning be a square partitioning, for which is no square partitioning that is made of a lesser number of squares.
Illustration:
Top row: The almost-square-rectangles of widths $3$, $4$ and $5$. Bottom row: Are these miminum-square-partitions of their corresponding rectangles?
My question is now:
What is the minimum-square-partitioning of an almost-square-rectangle?
Can we prove ${\rm M{\small IN}S{\small QUARES}}(R_{w,h=w-1})=w$?
Note a follow-up question, Minimum square partitions for 4x3 and 5x4 rectangles.
Solution
A similar question was asked on Mathoverflow. The commenters mentioned a paper of Kenyon, which shows that the minimum number of squares required to tile a $w \times (w-1)$ rectangle is $\Theta(\log w)$. See also a related paper of Walters.
You can tile a $(4t+7) \times (4t+6)$ rectangle using only $t+5$ squares (for $t \geq 0$).
You can tile a $(4t+7) \times (4t+6)$ rectangle using only $t+5$ squares (for $t \geq 0$).
Context
StackExchange Computer Science Q#16826, answer score: 6
Revisions (0)
No revisions yet.