My problem:

  • Dissect a grid polygon into rectangles. (A grid polygon is a rectilinear polygon all of whose vertices have integer coordinates.)

  • The rectangles must be taken from a predefined set (which includes a 1×1 rectangle, so the dissection is always possible).

  • Each rectangle has a cost which is not directly proportional to its size (a 2×3 rectangle may cost less 'per grid square covered' than a 1×1 rectangle).

  • No gaps or overlaps are allowed.

  • The optimal solution is the cheapest that covers the area.

My first thoughts were to work out the cheapest 'per square covered' rectangle and fit as many of those into the area as possible, but it seems that might perform poorly if it means filling a lot of spaces with small, expensive pieces.

I realise this is likely NP-hard, so I am probably looking for a heuristic rather than an algorithm. It seems in some ways similar to a bin-packing problem or a knapsack problem, but I can't see how to extend the solutions to these problems. I may just be lacking the right terminology, so if anyone could point me in the right direction to get started, I'd be grateful.


migrated from stackoverflow.com Mar 26 '12 at 19:05

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ Your solutions sounds like the simplest way to do it. It follows the standard greedy solution pattern - sort, then start going from best to worst. Try just sorting the rectangle list by efficiency (cost / space covered) and going from there. $\endgroup$ – bob_twinkles Mar 16 '12 at 3:09
  • $\begingroup$ It's normal to use the terms dissection when overlaps are forbidden (as in this case) and cover when overlaps are allowed. I changed the title accordingly. $\endgroup$ – Gareth Rees Mar 16 '12 at 10:26
  • 1
    $\begingroup$ If the set of rectangles were unconstrained, and every rectangle had the same cost, then this answer would explain how to compute the cheapest dissection. $\endgroup$ – Gareth Rees Mar 16 '12 at 10:30
  • $\begingroup$ Consider simulated annealing for this. $\endgroup$ – DeepYellow Mar 16 '12 at 20:28
  • $\begingroup$ I'm considering experimenting with this using simulated annealing. Do you have any sample data, and an appropriate cost function? $\endgroup$ – DeepYellow Mar 17 '12 at 7:51

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.