There is an $\text{N} \times \text{N}$ grid of squares. Some arbitrary subset of those squares must be covered by some number of rectangles (a given square must be covered entirely by one rectangle, rectangles can only cover these ares, not anything else). How can I find the set of rectangles that covers all of a given set of squares with the smallest possible number of rectangles?

What is the maximum number of rectangles needed to fill in any subset of an $\text{N} \times \text{N}$ square?


This is the Rectilinear Picture Compression problem that is known to be NP-hard (see textbook Computer and Intractability, a guide to the theory of NP-completeness by Garey and Johnson, p. 232, SR25). So noone will give you polynomial time solution if $\mathrm{P} \ne \mathrm{NP}$. You can apply methods for solving NP-hard problems, e. g., brunch and bounds.

EDIT: The note above was about cover-version of problem. For partition-version there are polynomial time algorithms. You can start from Efficient Algorithms for Geometric Graph Search Problems by Hiroshi Imai and Takao Asano, subsection 7.1. As far as I see for your case it provides $O(N^{5/2})$-time algorithm for a single connected region of squares and therefore $O(N^{7/2})$-time in total.

It seems that painting grid like chess board gives maximum number $\left\lceil\frac{N^2}2\right\rceil$ of rectangles needed, however I can't give rigorous proof now.

  • $\begingroup$ Wouldn't it be (N^2)/2, not (N/2)^2? I agree that this is probably the worst case, and that shouldn't be too hard to prove. $\endgroup$ Apr 10 '17 at 14:33
  • $\begingroup$ Yes, it's my bad. $\endgroup$
    – Smylic
    Apr 10 '17 at 14:39
  • $\begingroup$ The Rectilinear Compression problem seems to deal with cases where a new rectangle may cover up previously defined rectangles. This is not the case for my problem, which I think may be much easier. $\endgroup$ Apr 10 '17 at 14:56
  • $\begingroup$ So did you mean partition of set of squares into rectangles rather than covering it by rectangles? $\endgroup$
    – Smylic
    Apr 10 '17 at 15:06
  • $\begingroup$ Yes, that is what I mean. $\endgroup$ Apr 11 '17 at 23:24

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.