<p>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)$). </p>

<p>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). </p>

<p><a href="http://www.cims.nyu.edu/~esther/Publications/AronovEzraSharir.pdf" rel="nofollow">http://www.cims.nyu.edu/~esther/Publications/AronovEzraSharir.pdf</a></p>

CC BY-SA 3.0
2013-05-10T06:13:44.137Z
Why $\varepsilon$-net is relevant? Can you please elaborate a little?
Lu Wang
CC BY-SA 3.0
2013-05-11T22:37:56.163Z
Computing eps-net is equivalent to computing the rounding of an LP. See slide 11 here: http://valis.cs.uiuc.edu/~sariel/papers/10/barriers/barriers.pdf
Sariel Har-Peled
CC BY-SA 3.0
2013-05-10T04:38:42.987Z
2013-05-10T04:38:42.987Z
Sariel Har-Peled
<p>Suppose there are N orthogonal rectangles on the planes, overlapping or not.</p>

<p>I want to cover them with exact K orthogonal rectangles, overlapping or not. Each input rectangle must be completely covered. More specifically:</p>

<ul>
<li>An input rectangle can be covered by more than one covering rectangles.</li>
<li>An input rectangle may be partially covered by a covering rectangle.</li>
</ul>

<p>The target is to minimize the sum of the area of the covering rectangles.</p>

<p>Here is an example:</p>

<p><a href="https://i.sstatic.net/VLz63.png" rel="nofollow noreferrer">https://i.sstatic.net/VLz63.png</a></p>

<p>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.</p>

<p>I tried to google this, but not sure about the name of this problem. I got many results about the problem to <em>decompose</em> 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.</p>

<p>I guess this is NP-Hard or similar, so I don't even expect a good approximation. Any heuristic idea would be appreciated.</p>

<p>Thanks!</p>

CC BY-SA 3.0
2013-05-08T15:25:04.760Z
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.  http://scholar.google.com/scholar?cluster=17759953526391047560&hl=en&as_sdt=0,5 (and followups)
Neal Young
CC BY-SA 3.0
2013-05-08T15:33:07.627Z
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)$
Suresh Venkat
CC BY-SA 3.0
2013-05-08T15:37:36.253Z
@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.
Lu Wang
CC BY-SA 3.0
2013-05-08T19:47:26.717Z
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...)
Neal Young
CC BY-SA 3.0
2013-05-09T07:26:45.010Z
@NealYoung Yes, that's a good idea. Since there are O(N^4) possible covering rectangles, LP could be solved in polynomial time.
Lu Wang
CC BY-SA 3.0
2013-05-10T04:28:58.570Z
@NealYoung Constant approximation visa VC dimension arguments seems unlikely. Set systems involving rectangles are nasty. http://arxiv.org/abs/1012.1240
Sariel Har-Peled
<cg.comp-geom><approximation-algorithms>
Minimum-area orthogonal rectangle coverage
Lu Wang
# Minimum-area orthogonal rectangle coverage

(Asked by: username_0 on 2013-05-08)

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:

<https://i.sstatic.net/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!

**Tags:** cg.comp-geom, approximation-algorithms

> **Comments:**
> **username_1**: 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.  http://scholar.google.com/scholar?cluster=17759953526391047560&hl=en&as_sdt=0,5 (and followups)  
> **username_2**: 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)$  
> **username_0**: @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.  
> **username_1**: 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...)  
> **username_0**: @NealYoung Yes, that's a good idea. Since there are O(N^4) possible covering rectangles, LP could be solved in polynomial time.  
> **username_3**: @NealYoung Constant approximation visa VC dimension arguments seems unlikely. Set systems involving rectangles are nasty. http://arxiv.org/abs/1012.1240  

---

## 1 answers

### Answer by username_3 on 2013-05-10. Score: 2

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>

> **Comments:**
> **username_0**: Why $\varepsilon$-net is relevant? Can you please elaborate a little?  
> **username_3**: Computing eps-net is equivalent to computing the rounding of an LP. See slide 11 here: http://valis.cs.uiuc.edu/~sariel/papers/10/barriers/barriers.pdf  

---

