1
$\begingroup$

There are two ways to cover a geometric shape with primitive units: you can allow the units to overlap, or require that they be disjoint. Of course the number of units in the case of disjoint covering may be larger. But how much larger?

If the units are squares, the number of units in a disjoint covering might be arbitrarily larger. For example, consider an $n\times (n+1)$ rectangle. For every $n$, it can be covered by two overlapping squares. But if the squares have to be disjoint, at least $O(\log n)$ squares are required.

What if the units are rectangles? Is there a sequence of shapes that can be covered by two rectangles, but whose disjoint-rectangles-cover-number can be arbitrarily large?

EDIT: This question is related: Tiling an L-shape with "almost square"s

$\endgroup$
1
$\begingroup$

I suspect that if you take two $1 \times 4$ strips of paper, call them $A$ and $B$, and lay out one horizontally, and the other rotated by, say, 30 degrees, but crossing over the first, so that they form a kind of squashed "X" shape, you get something that can be covered by two rectangles (the two strips $A$ and $B$), but may not be coverable by any finite number of disjoint rectangles -- the sharp corners of $B - A$ seem likely to make this impossible.

Indeed, if you think of a connected disjoint union of finitely many rectangles that forms a simple polygon, then each vertex of the polygon must be adjacent to one or more rectangles of the decomposition; each such rectangle must contribute an angle of 90 or 180 degrees, so that it's impossible, for example, to write an equilateral triangle as a disjoint union of rectangles. This idea, applied to the "cross" above, shows that the non-90-degree corners of the "cross" prevent the cross's being decomposed into disjoint rectangles.

$\endgroup$
  • $\begingroup$ This makes sense, thanks. It seems the example must involve rotated rectangles (in contrast to the square case), since if the rectangle are parallel to each other, their intersection is also rectangular. $\endgroup$ – Erel Segal-Halevi Jul 22 '14 at 15:43
  • $\begingroup$ Well...this example's proof uses the fact that there are non-90-degree corners, but that doesn't preclude the possibility that there's some example that uses aligned rectangles...I just can't think of one. :) $\endgroup$ – John Hughes Jul 22 '14 at 17:45

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.