Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
Somewhat similar... –  J. M. Sep 13 '11 at 16:55
    
I take it the rectangles cannot be rotated to improve the covering? –  hardmath Sep 13 '11 at 16:59
    
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. –  Joseph O'Rourke Sep 13 '11 at 18:50
    
@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. –  EvilAmarant7x Sep 14 '11 at 13:08
    
@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. –  Joseph O'Rourke Sep 14 '11 at 23:49
show 2 more comments

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.