# Minimum-area orthogonal rectangle coverage

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:

http://i.stack.imgur.com/VLz63.png

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.

Thanks!

• Perhaps the approximation algorithm for set cover for set systems with bounded VC dimension applies. I expect it gives a constant-factor approximation for a closely related problem. scholar.google.com/… (and followups) May 8 '13 at 15:25
• Note that for $k=1$ this can be done in polynomial time. So you might even reasonably expect something that's $2^k \cdot \text{poly}(n)$ May 8 '13 at 15:33
• @NealYoung I think the set cover problem is related to those problems I found, but not my problem. I'm fixing the number of covering rectangles and the target is minimize the total area. Maybe the knapsack problem is related. May 8 '13 at 15:37
• For a heuristic you could solve the LP and round it. (The LP that has an indicator variable for each of the poly-many possible rectangles you might use in the k-cover, a constraint for each rectangle that needs to be covered, a constraint that the sum of the variables equals k, and the natural objective...) May 8 '13 at 19:47
• @NealYoung Constant approximation visa VC dimension arguments seems unlikely. Set systems involving rectangles are nasty. arxiv.org/abs/1012.1240 May 10 '13 at 4:28

See the paper by Aronov, Ezra and Sharir. They handle the case for points. For rectangles it is not even immediately obvious that an LP relaxion is easy to do, since there might be a chaining effect, and as such the number of candidate rectangles might be large (i.e., $O(n^k)$).
A solution with $O(k \log k)$ rectangles with the same area as the optimal solution, should follow by using BSP (binary space partition) and dynamic programming in polynomial time. So searching on the web would give you refs to papers using this scheme (I dont remember the ref, sorry).
• Why $\varepsilon$-net is relevant? Can you please elaborate a little? May 10 '13 at 6:13