Given an $M$x$N$ grid with some predefined sub-rectangles. How to divide the grid into a set of sub-rectangles, which contains the predefined sub-rectangles, so that its the number of elements is minimum and no sub-rectangle is overlapped ?

Is there any reference to the problem and it's solutions ? Is the problem NP-Hard ?

For example: A grid contains 2 predefined (black) sub-rectangles might be divided as follow: enter image description here

  • $\begingroup$ Had I had time, I would have written an algorithm of linear-log time-complexity. $\endgroup$ – John L. Sep 9 '18 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.