Algorithms for covering a rectilinear polygon using the same multiple rectangles

Question

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!

Answer 1

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:

"Given points in a Euclidean space (in this application, on a grid), find a minimally sized set of squares of prescribed size covering all those points."

This is quoted from the paper, "Approximation schemes for covering and packing problems in image processing and VLSI," by Hochbaum and Maass, 1985 (ACM link), in which they offer a polynomial-time approximation scheme (i.e., a PTAS).

If one seeks a minimal cover by squares of perhaps different sizes, then the problem can be solved in polynomial time for polygons without holes, but is NP-complete for polygons with holes. This is discussed in an earlier MO question, "Covering an arbitrary polygon with minimum number of squares."

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.