Given some polygon and rectangles all of a fixed height and width, how I can calculate the number and placement of the rectangles so that no point within or on the polygon is not contained within at least one rectangle. The rectangles are allowed to contain area that is not contained by the polygon and are allowed to overlap. The polygon can't be self-intersecting, but other than that anything goes. The polygon lies on a grid, there is given list of the polygon's vertices, and the rectangle's lengths are defined in grid units.

This abstract here seems to cover the topic I'm interested in, but I can't seem to find anything beyond the abstract.


  • $\begingroup$ Somewhat similar... $\endgroup$ – J. M. is a poor mathematician Sep 13 '11 at 16:55
  • $\begingroup$ I take it the rectangles cannot be rotated to improve the covering? $\endgroup$ – hardmath Sep 13 '11 at 16:59
  • $\begingroup$ The abstract to which you refer (by Hoffmann) is specialized to covering by two or three congruent rectangles. The general problem is NP-complete if the rectangles must be inside the polygon. As Robert suggests, your problem is almost surely NP-hard, so you need to look at approximation algorithms. $\endgroup$ – Joseph O'Rourke Sep 13 '11 at 18:50
  • $\begingroup$ @Joseph I know I can use a greedy approximation for sets of elements, but I'm not sure how to extend it to polygon coverings. $\endgroup$ – EvilAmarant7x Sep 14 '11 at 13:08
  • $\begingroup$ @Evil: The greedy algorithm is essentially the best one can achieve for an arbitrary set-cover problem. Yours is not arbitrary, but it may be difficult to exploit its non-arbitrariness. You could exploit the grid, perhaps, especially if its size is not too large. $\endgroup$ – Joseph O'Rourke Sep 14 '11 at 23:49

You might look up "set covering problems". I would expect that your problem would be NP-complete.


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.