# Help in NP-Hardness proof of a certain type of Class Cover problem

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.

• 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 Apr 18 '14 at 15:21
• 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 Apr 18 '14 at 15:46
• @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 Apr 19 '14 at 7:43
• @SureshVenkat I didn't understand the last line. – srkaysh Apr 19 '14 at 7:47
• @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 Apr 19 '14 at 7:57