Consider a problem in which you are given a 2D grid (e.g. a chessboard) where certain squares are occupied and you need to put the minimum number of non-overlapping rectangles of any size w x h where w = 1 or h = 1 (i.e. "square segments") such that all unoccupied squares are covered and each rectangle covers only unoccupied squares.

For example, for the grid


the solution would be 4, since you can cover all the unoccupied squares (denoted by '.') with 4 such rectangles as follows:


I tried to come up with a polynomial algorithm or prove that this problem is NP-hard, but without success. Can anyone help me to prove / disprove that this is problem is in P, or point me to some related work / problems?

  • 2
    $\begingroup$ Can rectangles also cover occupied squares? Also, can rectangles overlap? The way you presented the solution of the example suggests that neither is allowed, but your problem statement does not say any restriction. $\endgroup$ – Tsuyoshi Ito Feb 18 '13 at 23:35
  • $\begingroup$ Correct, neither is allowed. I'm going to update the problem statement. $\endgroup$ – eold Feb 18 '13 at 23:37

Ok, so you have a polygon $P$ with integer-length axis-parallel sides and possibly with holes (the shape you want to cover) and you want to partition it into as few $1\times a$ or $b\times 1$ rectangles as possible. At first I thought you wanted the minimum partition into rectangles of arbitrary shapes, which has a known polynomial time solution involving a reduction to maximum independent sets in bipartite graphs. But I think this one is also polynomial, via a different reduction to the same problem.

Draw a graph $G$ that has a vertex for every unit-length line segment that separates two squares of $P$, and that has an edge connecting the vertices for every two perpendicular line segments that share an endpoint. Then the partitions of $P$ into unit-width rectangles correspond one-for-one with independent sets of $G$. If a vertex $v$ of $G$ corresponds to a line segment $s$, then $v$ belongs to a given independent set exactly when the two squares separated by $s$ belong to the same rectangle as each other in the corresponding partition.

Under this correspondence, we have the equation $R=S-I$ where $R$ denotes the number of rectangles in a given partition, $S$ denotes the number of squares in $P$, and $I$ denotes the cardinality of the independent set; this is easy to see by induction on $I$, by removing one independent set element at a time. Since $S$ is fixed, minimizing $R$ is the same as maximizing $I$, and the optimal partition of $P$ corresponds to the maximum independent set of $G$. But $G$ is a bipartite graph (horizontal segments are adjacent only to vertical segments and vice versa) so its maximum independent set may be found in polynomial time (see König's theorem on Wikipedia).

| cite | improve this answer | |

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.