Inapproximability of the Perimeter Defense Problem
Evangelos Kranakis, Danny Kriz̧anc, Lata Narayanan, Kun Xu · 2009
We model the problem of detecting intruders using a set of infrared beams by the perimeter defense problem: given a polygon P, find a minimum set of edges S of the polygon such that any straight line segment crossing the polygon intersects at least one of the edges in S. We observe that this problem is equivalent to a new hiding problem, the Max-Hidden-Edge-Set problem. We prove the APX-hardness of the Max-Hidden-Edge-Set problem for polygons without holes and rectilinear polygons without holes, by providing gap-preserving reductions from the Max-5-Occurrence-2-Sat problem. 1