2
$\begingroup$

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.

Thanks!

  • 0
    @hardmath Yes, the rectangle's vertices lie on the grid. I ended up just finding the bounding rectangle for the polygon, tiling the covering rectangles over that bounding rectangle, and then discarding any covering rectangles that didn't intersect or lie within the polygon.2011-09-19

1 Answers 1

1

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