Inapproximability results for guarding polygons and terrains

Past research on art gallery problems has concentrated almost exclusively o n bounds on the numbers of guards needed in the worst case in various setti ngs. On the complexity side, fewer results are available. For instance, it has long been known that placing a smallest number of guards for a given in put polygon is NP-hard. In this paper we initiate the study of the approxim ability of several types of art gallery problems. Motivated by a practical problem, we study the approximation properties of the three art gallery problems VERTEX GUARD, EDGE GUARD, and POINT GUARD. W e prove that if the input polygon has no holes, there is a constant delta > 0 such that no polynomial time algorithm can achieve an approximation ratio of 1+delta, for each of these guard problems. We obtain these results by p roposing gap-preserving reductions from 5-OCCURRENCE-MAX-3-SAT. We also prove that if the input polygons are allowed to contain holes, then these problems cannot be approximated by a polynomial time algorithm with ratio ((1 - epsilon)/12) In n for any epsilon >0, unless NP subset of TIME( n(O(logLog n))), where n is the number of vertices of the input polygon. We obtain these results by proposing gap-preserving reductions from the SET C OVER problem. We show that this inapproximability for the POINT GUARD problem for polygon s with holes carries over to the problem of covering a 2.5-dimensional terr ain with a minimum number of guards that are placed at a certain fixed heig ht above the terrain. The same holds if the guards may be placed on the ter rain itself.