Polygon Cover Input A set of points P a set of polygons S in

Polygon Cover:

Input: A set of points P, a set of polygons S in a 2D plane, and a positive integer k?N.

Output: True if and only if there exists a subset in S of at most k (not necessarily convex) polygons such that every point in P lie inside some polygon in the subset.

I am trying to give a polynomial reduction from Vertex Cover to Polygon Cover. However, I am struggling slightly. My idea is that to construct the set of points P, I figured that I should map each uv?E with (u<v) to a point (u,v). For the set of polygons S, I was thinking to define some type of non-convex polygon in order to cover the rows and columns.

Solution

Let (G,k) be an instance of Dominating Set where G is drawn on the plane with any drawing. Construct for each vertex v a polygon Sv which covers all of N[v] and no other vertices, where N[v] is the set containing v and all its neighbors. Let S=?v?V(G)Sv and the points P be the points where the vertices are drawn. The instance for Polygon Cover is P,S,k. This reduction is a Karp-reduction from Dominating Set which is NP-complete, and hence Polygon Cover is NP-complete as well.

To formally prove that the above reduction works, you need to prove that selecting a set of k polygons S??S which covers all the points corresponds to picking a set of vertices whose neighborhoods contain all the vertices of the graph.

If you want to prove it for convex polygons, you can use the fact that Dominating Set is NP-complete on planar graphs and that planar graphs are equivalent to kissing graphs.