Introduction

Complexity
The Art-Gallery

The Proofs
Conclusions

References

NP-Hardness for Polygons with Holes



The proof will consist of a reduction from 3SAT. Recall the definition:
3-SATISFIABILITY (3SAT)
Instance: Set U of variables, a collection C of clauses over U such that each clause c in C has size exactly 3.
Question: Is there a truth assignment for U satisfying C?

We introduce the problem:
Minimum Star (or Guard) Cover of a Polygon with Holes (StarCH)
Instance: A set of lists of vertices representing a polygonal region P and a positive integer bound K.
Question: Is there a cover of P with K or fewer star subsets of P, i.e., do there exist star polygons S1, S2, S3, ..., Sk with k less than K such that their union is P?


Claim: StarCH is NP-hard
Proof:
For each literal in U, we create a repetitive staircase pattern with only two possible minimum star covers (Fig 1-a). One cover will be associated to true and one to false (Fig 1-b,c).


Fig 1-a: Polygon to represent a literal.



Fig 1: a) The polygon cover corresponding to true and b) the one corresponding to false


The dots and numbers associated with them are not part of the construction. They are needed for the purposes of the proof. Note that two points are covered by one star-polygon if and only if they are consecutive numbers.



These staircases will be bent to form closed loops. There will be one loop for every variable in the formula. This represents the choice of xi or its negation. Before we continue, let us show that we can form these loops.



Claim: The variable loops can be bent 45o without altering their properties.
Proof:
See Figure 2 below.


Fig 2: A loop bending 45o without losing any properties




It is not hard to see that applying many such bends will form a loop suitable for our purposes. Next we address the fact that we need to cross some variable loops, again, without altering their coverage properties.



Claim: Two variable loops may cross without affecting the numbers of star polygons in their minimum coverage nor their true/false assignment.
Proof:


Fig 3: 2-loop Crossover

Refer to figure 3. Most cases are trivial except for the one where i and j in the figure could be covered by one star polygon. To avoid this, we can arrange it so that each crossover occurs where i and j are both odd, ensuring this case never arrises.



Examine the region Q where the crossing occurs. It must contain exactly one of the numbered points from each of the two variable loops. Both of these are odd by our construction. Since no star polygon can contain more than one even numbered point in our staircase structure, and since there are K even distinguished points, every cover must contain K stars to cover those even points. So if a cover also includes Q (and possibly other crossings like Q) then it must have more than K elements.



Now we address the clauses and their role. We will add isoceles triangles at corners of the variable loops. The triangles will be covered for free by a star polygon by only one of the two possible truth assignments. An example is shown in Fig 4.


Fig 4: A variable loop with an added isosceles triangle guardable for free by only one assignment



Fig 5: Triangular regions combined to create a clause junction




We expand on this in figure 5 and turn those triangles into clause junctions. The center triangle can be covered for free if the clause is satisfied and remains uncovered if not. Also, the junction does not effect the coverage properties of the variable loops.



Overall, our polygon will resemble something like what is in figure 6. Namely, literal loops turning to hit clause triangles crossing others at odd distinguished regions only.


Fig 6: The final polygon configuration as seen from afar




Finally, if r is the number of numbered points in a variable loop, the number of star polygons needed to cover that loop is r/2. So the sum of the r/2's over all variable loops will be our K.



The specified construction will require no more than O(m) bends, O(mn) crossovers and O(m) clause junctions where m is the number of clauses and n is the number of variables. So this construction is polytime. We see that for any satisfying assignment to the boolean formula, we can choose the corresponding star cover of each variable loop. Since we know that each clause is satisfied, all the clause triangles are covered by construction. So it must be that the polygon we contructed has a star cover of the appropriate number.



Assume there is star cover of the appropriate size for the constructed polygon. Then it must be that for each variable loop we've chosen one of the two possible star covers since they are the only way to cover the loops. Since there is a star cover, there must be a way to choose the variable loop covers such that the clause triangles are covered. So, we choose the variable cover's corresponding true/false value to be our variable assignment. We know that it must satisfy the formula since all the clause junctions were covered.



So we can now conclude that the StarCH problem is NP-hard.