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.

  • 1
    $\begingroup$ 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). $\endgroup$ – Marzio De Biasi Apr 18 '14 at 15:21
  • 2
    $\begingroup$ 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 ? $\endgroup$ – Suresh Venkat Apr 18 '14 at 15:46
  • $\begingroup$ @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. $\endgroup$ – srkaysh Apr 19 '14 at 7:43
  • $\begingroup$ @SureshVenkat I didn't understand the last line. $\endgroup$ – srkaysh Apr 19 '14 at 7:47
  • $\begingroup$ @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) $\endgroup$ – Marzio De Biasi Apr 19 '14 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.