<p>Class Cover Problem is nothing but finding an optimal cover of certain class (Point Set) with a particular shape only i.e. finding minimum number of a certain shaped polygon (for example, rectangle) required to cover the Point Set (S).</p>

<p>Well, covering by Rectangles is proved to be NP-Hard and now, I want to consider a different shape say L-shape and now find out covering by it. </p>

<p>So, can somebody help me in proving that this problem is NP-Hard too. I've worked on it a bit, tried reducing it from known NP-Hard problem but couldn't quite get it.</p>

CC BY-SA 3.0
2014-04-18T15:21:14.947Z
The L-shape is a generalization of the rectangle shape; so (unless I'm missing something) the NP-hardness proof comes for free. If you're not convinced just use an L shape in which the top width and the base width differs only by a small quantity that cannot influence the covering (the difference between the top width and bottom width of the Ls is only a small fraction of the distances between points and/or rectangle sizes used in the source instance of rectangle cover problem).
Marzio De Biasi
CC BY-SA 3.0
2014-04-18T15:46:08.403Z
Actually here's a question that might be interesting: Suppose I know that finding a minimal cover of a base set by a class of shapes is NP-hard. Can I automatically say anything about a class of shapes formed by taking constant-sized unions over the original class ?
Suresh Venkat
CC BY-SA 3.0
2014-04-19T07:43:49.673Z
@MarzioDeBiasi well, you see that was the first thought for tackling this problem but according to your approach, it says size of the optimal cover by L-shape is always equal to the size of the cover by rectangles. But that is true for some cases and for some the size reduces for L-shape.

So, considering rectangles as an L-shape is wrong.
srkaysh
CC BY-SA 3.0
2014-04-19T07:47:51.743Z
@SureshVenkat I didn't understand the last line.
srkaysh
CC BY-SA 3.0
2014-04-19T07:57:04.513Z
@DeAtHvAdEr: perhaps I misunderstood the problem: is the size of the L shapes given as input and fixed? (in this case my approach should work to prove NP-hardness) Or can they be arbitrary? (perhaps you could formally define the L-shape cover problem in the question to avoid confusion)
Marzio De Biasi
CC BY-SA 3.0
2014-04-19T08:05:55.250Z
@MarzioDeBiasi: In simple words, input is a set of points and I need to cover that with 'k' no. of axis-parallel L-shaped polygons (size of each polygon can vary) and now I have to find min(k) possible.
srkaysh
CC BY-SA 3.0
2014-04-19T08:16:04.280Z
@srkaysh your $L$-shaped polygon is a union of two rectangles (a very special union). I was merely wondering about a more general variant, when the union could be of more than two (but a constant number of) things.
Suresh Venkat
CC BY-SA 3.0
2014-04-19T08:21:48.793Z
@srkaysh: but it's not clear, if the size of the L shapes can be arbitrary, you just need only one big L. So the size must be part of the input, and if the proportion between the base width and the top width is not fixed, then my reduction works (if it is fixed, e.g. 1:2, then it doesn't work). I suggest to formally define your problem in the question using the Garey&Johnson style (Input: .... Question: ....).
Marzio De Biasi
<np-hardness>
Help in NP-Hardness proof of a certain type of Class Cover problem
srkaysh
# Help in NP-Hardness proof of a certain type of Class Cover problem

(Asked by: username_0 on 2014-04-18)

Class Cover Problem is nothing but finding an optimal cover of certain class (Point Set) with a particular shape only i.e. finding minimum number of a certain shaped polygon (for example, rectangle) required to cover the Point Set (S).

Well, covering by Rectangles is proved to be NP-Hard and now, I want to consider a different shape say L-shape and now find out covering by it.

So, can somebody help me in proving that this problem is NP-Hard too. I've worked on it a bit, tried reducing it from known NP-Hard problem but couldn't quite get it.

**Tags:** np-hardness

> **Comments:**
> **username_1**: The L-shape is a generalization of the rectangle shape; so (unless I'm missing something) the NP-hardness proof comes for free. If you're not convinced just use an L shape in which the top width and the base width differs only by a small quantity that cannot influence the covering (the difference between the top width and bottom width of the Ls is only a small fraction of the distances between points and/or rectangle sizes used in the source instance of rectangle cover problem).  
> **username_2**: Actually here's a question that might be interesting: Suppose I know that finding a minimal cover of a base set by a class of shapes is NP-hard. Can I automatically say anything about a class of shapes formed by taking constant-sized unions over the original class ?  
> **username_0**: @MarzioDeBiasi well, you see that was the first thought for tackling this problem but according to your approach, it says size of the optimal cover by L-shape is always equal to the size of the cover by rectangles. But that is true for some cases and for some the size reduces for L-shape.  So, considering rectangles as an L-shape is wrong.  
> **username_0**: @SureshVenkat I didn't understand the last line.  
> **username_1**: @DeAtHvAdEr: perhaps I misunderstood the problem: is the size of the L shapes given as input and fixed? (in this case my approach should work to prove NP-hardness) Or can they be arbitrary? (perhaps you could formally define the L-shape cover problem in the question to avoid confusion)  
> **username_0**: @MarzioDeBiasi: In simple words, input is a set of points and I need to cover that with 'k' no. of axis-parallel L-shaped polygons (size of each polygon can vary) and now I have to find min(k) possible.  
> **username_2**: @username_0 your $L$-shaped polygon is a union of two rectangles (a very special union). I was merely wondering about a more general variant, when the union could be of more than two (but a constant number of) things.  
> **username_1**: @username_0: but it's not clear, if the size of the L shapes can be arbitrary, you just need only one big L. So the size must be part of the input, and if the proportion between the base width and the top width is not fixed, then my reduction works (if it is fixed, e.g. 1:2, then it doesn't work). I suggest to formally define your problem in the question using the Garey&Johnson style (Input: .... Question: ....).  

---

## 0 answers

