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!
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). 

http://www.cims.nyu.edu/~esther/Publications/AronovEzraSharir.pdf