Inapproximability of the perimeter defense problem
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.
|Conference||21st Annual Canadian Conference on Computational Geometry, CCCG 2009|
Kranakis, E, Krizanc, D. (Danny), Narayanan, L. (Lata), & Xu, K. (Kun). (2009). Inapproximability of the perimeter defense problem. Presented at the 21st Annual Canadian Conference on Computational Geometry, CCCG 2009.