Finding minimum hidden guard sets in polygons—tight approximability results

We study the problem Minimum Hidden Guard Set, which consists of positioning a minimum number of guards in a given polygon (or other structure such as a terrain) such that no two guards see each other and such that every point in the polygon is visible from at least one guard. By constructing a gap-creating reduction from 5-Occurrence-3-Satisfiability, we show that this problem cannot be approximated by any polynomial-time algorithm with an approximation ratio of |I|1−ϵ for any ϵ>0, unless NP=P, where |I| is the size of the input polygon. The result even holds for input polygons without holes, which separates the problem from other visibility problems such as guarding and hiding, where strong inapproximability results hold only for polygons with holes. We also show that a straight-forward approximation algorithm achieves an approximation ratio of |I|. These two results characterize the approximability threshold of Minimum Hidden Guard Set exactly up to low-order terms.