Hiding people in polygons (Q1122366): Difference between revisions

Given a polygon P, a hidden (vertex-) set is a set of points (vertices) such that no two points in the set are visible to each other. A (vertex-) guard set is a set of points (vertices) such that each point of P is visible to some point in the guard set. With the help of the NP- completeness of the problem 3-SAT the author shows that the problem of finding a maximum hidden set is NP-hard. A hidden guard set is a hidden set which is also a guard set. The problem of finding a minimum hidden guard set is shown to be NP-complete. For hidden vertex sets and hidden vertex guard sets similar results are obtained.