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!