Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Inapproximability Results for Guarding Polygons and Terrains
| |
|
Inapproximability Results for Guarding Polygons and Terrains
S. Eidenbenz1, C. Stamm1 and P. Widmayer1
| (1) |
Institute for Theoretical Computer Science, ETH Zentrum, 8092 Zürich, Switzerland. \{eidenben,stamm,widmayer\}@inf.ethz.ch., CH |
Abstract. Past research on art gallery problems has concentrated almost exclusively on bounds on the numbers of guards needed in the
worst case in various settings. 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 input polygon is NP -hard. In this paper we initiate the study of the
approximability 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. We prove that if the input polygon has no holes, there is a constant δ >0 such that no polynomial time algorithm can achieve an approximation ratio of 1+δ , for each of these guard problems. We obtain these results by proposing 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-ɛ)/12) \ln n for any ɛ > 0 , unless NP \subseteq TIME(n
O
(log log
n)
) , where n is the number of vertices of the input polygon. We obtain these results by proposing gap-preserving reductions from the
SET COVER problem.
We show that this inapproximability for the POINT GUARD problem for polygons with holes carries over to the problem of covering
a 2.5-dimensional terrain with a minimum number of guards that are placed at a certain fixed height above the terrain. The
same holds if the guards may be placed on the terrain itself.
Key words. Art gallery, Visibility problems, Inapproximability, Gap-preserving reductions, Terrains, Telecommunications.
Received September 22, 1999; revised December 5, 1999.
Fulltext Preview (Small, Large)
|
|
|
|
|
|