ABSTRACT: Define an "almost square" as a rectangles with aspect ratio in $[{1 \over 2},2]$. What is the minimal number of interior-disjoint almost-squares required to tile the following L-shape (where $n$ is an integer)?


INTRODUCTION: It is known (e.g. Richard Kenyon, 1996) that tiling an $n \times (n-1)$ rectangle with squares requires $O(\log n)$ squares. This number grows to infinity as $n$ grows. However, if we relax our requirements and agree to tile the rectangle with almost squares, then one almost-square is sufficient. In practical scenarios, almost-squares can be almost as good as squares, and their number (in this case) is significantly smaller.

MY QUESTION IS: Does this fact extend to more general polygons? Specifically, is it possible to tile the L-shape in the above diagram (which is an $n \times n$ square, missing a single $1 \times 1$ square at the corner) with axis-parallel almost-squares whose number is constant (independent of $n$)?

EDIT: This question is related: Size of minimal covering, overlapping and disjoint

  • $\begingroup$ It might help to include an example of an almost-square tiling to attract a wider audience. $\endgroup$ – Semiclassical Jul 22 '14 at 16:08

Your Answer

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

Browse other questions tagged or ask your own question.