Suppose there are N orthogonal rectangles on the planes, overlapping or not.
I want to cover them with exact K orthogonal rectangles, overlapping or not. Each input rectangle must be completely covered. More specifically:
- An input rectangle can be covered by more than one covering rectangles.
- An input rectangle may be partially covered by a covering rectangle.
The target is to minimize the sum of the area of the covering rectangles.
Here is an example:
The input consists of 3 rectangles as shown in the show. When k=1,2,3, the solutions are shown below. There are 2 possible solutions for K=3, depending on whose area is smaller. Note that an input rectangle can be partially covered by a covering rectangle.
I tried to google this, but not sure about the name of this problem. I got many results about the problem to decompose rectilinear polygons into rectangles, where the target is to minimize the number of covering rectangles used. That is not my case, I don't require that the covering rectangles are disjoint, and I want to minimize the area fixing the number of the covering rectangles instead of the opposite way.
I guess this is NP-Hard or similar, so I don't even expect a good approximation. Any heuristic idea would be appreciated.