# Algorithms for covering a rectilinear polygon using the same multiple rectangles

Sorry for the crossing-posting: original post is here

All angles of the polygon (representing a room) are right. It may be convex or concave. Use rectangles of the same size (representing a sensor coverage) to cover the polygon. The edge of the polygon and rectangle are parallel with the coordinate axis. Overlapping between rectangle is allowed. All rectangles are oriented in the same direction.

The objective is to minimize the number of rectangles and to minimize the overlap, i.e., the fewest rectangles given that the smallest overlap, or the smallest overlap given that, the fewest rectangles. Note that the rectangles can cover outside of the polygons, and also allow there may exist some gaps between rectangles. The constraints are not very strict in this problem because this is not a pure math problem.

I have no background with computational geometry. I searched online and find many algorithms use different rectangles to cover the polygon.

Does anyone know some algorithms to solve this? It would be better if anyone could provide the code of the algorithm. Many thanks!

• When cross-posting from MSE, the netiquette requires including the link: math.stackexchange.com/questions/409645/… – fedja Jun 2 '13 at 22:22
• @hujia06: Do you require that the rectangles be oriented the same way? That is, if they are $a \times b$, is the $a$-side always horizontal? – Joseph O'Rourke Jun 3 '13 at 0:11

Suppose the rectangle is $a \times b$. If all rectangles in the cover must be oriented identically, say, with the $a$-side horizontal, then by scaling the original polygon, the problem becomes covering by squares of a given size. This problem, is, I believe, NP-complete for polygons with holes, but might be polynomial for polygons without holes. This closely related problem is definitely NP-complete:
If the $a \times b$ rectangles can be oriented horizontally or vertically, then I suspect the problem is just as difficult, but I have no specific reference to offer at the moment.