Partioning rectangles into rectangles and valid sub-rectangle extension rules.

29 Views Asked by At

Given a rectangle $A$ composed of unit squares, we then fuse grid squares into sub-rectangles $B_i$ in a way that the $B_i$ partition $A$.

Example:

XXO
YZO
YWW

where each character represents a grid square and same characters together represent a $B_i$. An invalid example would be

wB
ww

because the 'w' characters don't form a rectangle.

Now define a rule whereby a $B_i$ may be extended into the next row or column (not both), taking away squares from adjacent rectangles to become a larger $B_i'$. Squares taken away from adjacent rectangles reduce their area or even lets them disappear. As an example, we extend the 'XX' rectangle first to the right and then downwards to get

XXO     XXX    XXX
YZO  -> YZO -> XXX
YWW     YWW    YWW

The extension to the right reduces the 'O' to one square and the extension downward lets 'Z' and 'O' disappear. But in both steps $A$ is partioned into rectangles.

An illegal extension would be to extend the 'w' rectangle to the right in the following setup:

wZZ     wwZ
OZZ  -> OZZ  (illegal)

because the 'Z' characters now longer form a rectangle.

Question: Is there a straightforward way to see that the extension of 'w' above is not allowed. Of course I can compute the extension and check that the set difference of 'Z' minus the extended 'w' is invalid. Yet I am wondering if there is some neat invariant that easily tells me that 'w' is downward extensible, but not rightward.

(I am really guessing the tags and would be happy to see corrections.)