A rectilinear polygon can be characterized by its cover number - the smallest number $k$ such that the polygon can be covered by $k$ possibly overlapping squares. For example:
- For a square, $k=1$.
- For a 2-by-1 or 2-by-3 rectangle, $k=2$.
- For a square missing a small square piece in one of the corners, $k=3$.
I would like to partition a polygon with cover number $k$ to two dijsoint pieces, such that the cover number or each piece is less than $k$. This is not always possible, for example:
- For a square, $k=1$ and it is obviously not possible to partition it to pieces with a smaller cover number.
- For a 2-by-3 rectangle, $k=2$ and it is not possible to partition it to two squares.
- For a square missing a rectangular non-square piece in one of the corners, $k=3$ and it is not possible (I think) to partition it to two pieces with cover number at most 2.
But my examples are only for small values of $k$.
MY QUESTION: Is there a certain $k_0$, such that every rectilinear polygon with cover number $k>k_0$ can be partitioned to two pieces with cover number less than $k$?
No.
Consider the polygon $P$ obtained by overlapping $k$ unit squares with lower left corners $(i\epsilon,i\epsilon)$, $0\le i<k$, where $\epsilon$ is small enough. Then from the $k$ corners of the top left "staircase" we see that $P$ has covering number $\ge k$. By construction, it os also $\le k$, hence $=k$. We could have made the same argument with the $k$ lower right corners, but of course these are covered by the same $k$ squares.
Assume we can decompose $P$ into $P_1,P_2$ with cover number $<k$ each. Then the $k$ top left / lower right corners of $P$ also occur as such in one of the $P_i$. Say $P_i$ inherits $a_i$ top left and $b_i$ lower right corners. Then $a_1+a_2=b_1+b_2=k$ and $a_1,a_2,b_1,b_2<k$. From the latter we conclude $a_1,a_2,b_1,b_2\ge1$ and hence $P_1,P_2$ have diameter $\ge\sqrt 2$. As $(a_1+b_1)+(a_2+b_2)\ge 2k$, we may assume wlog. that $a_1+b_1\ge k$. Then at least one of the covering squares for $P_1$ must cover both a top left and a lower right corner, hence must be a unit square. Then $P_2$ is contained in an L-shaped part of thickness $(k-1)\epsilon$, hence the $k-1$ covering squares for $P_2$ have side length $\le(k-1)\epsilon$ and hence the diameter of $P_2$ is $\le (k-1)\epsilon\sqrt 2$. If $\epsilon<\frac1{k-1}$ this gives us a contradiction.