Terrain Guarding Problem(TGP), which is known to be NP-complete, asks to find a smallest set of guard locations on a terrain T such that every point on T is visible by a guard. Here, we study this problem on 1.5D orthogonal terrains where the edges are bound to be horizontal or vertical. We propose a 2-approximation algorithm that runs in O(nlog m) time, where n and m are the sizes of input and output, respectively. This is an improvement over the previous best algorithm, which is a 2-approximation with O(n 2 ) running time.
The terrain guarding problem is closely related to the well known Art Gallery Problem @cite_7 of finding the minimum set of positions to guard a polygon. The first result was obtained by Chv 'atal: @math guards are always sufficient and sometimes necessary to guard a polygon of n vertices. Art Gallery Problem was shown to be NP-hard: on simple polygons @cite_12 , on simple orthogonal polygons @cite_0 , and on monotone polygons @cite_3 . Moreover, it was shown to be APX-hard on simple polygons @cite_2 .
@cite_7 @cite_3 @cite_0 @cite_2 @cite_12
2063442090 2004151341 2060049097 2502636724
We study the computational complexity of the art gallery problem originally posed by Klee, and its variations. Specifically, the problem of determining the minimum number of vertex guards that can see an n -wall simply connected art gallery is shown to be NP-hard. The proof can be modified to show that the problems of determining the minimum number of edge guards and the minimum number of point guards in a simply connected polygonal region are also NP-hard. As a byproduct, the problem of decomposing a simple polygon into a minimum number of star-shaped polygons such that their union is the original polygon is also shown to be NP-hard. A set @math of points on a terrain, also known as an @math -monotone polygonal chain, is said to guard the terrain if every point on the terrain is seen by a point in @math . Two points on the terrain see each other if and only if the line segment between them is never strictly below the terrain. The minimum terrain guarding problem asks for a minimum guarding set for the given input terrain. Using a reduction from PLANAR 3-SAT we prove that the decision version of this problem is NP-hard. This solves a significant open problem and complements recent positive approximability results for the optimization problem. 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. In 1973, Victor Klee posed the following question: How many guards are necessary, and how many are sufficient to patrol the paintings and works of art in an art gallery with n walls? This wonderfully naive question of combinatorial geometry has, since its formulation, stimulated a plethora of papers, surveys and a book, most of them written in the last fifteen years. The first result in this area, due to V. Chvatal, asserts that n 3 guards are occasionally necessary and always sufficient to guard an art gallery represented by a simple polygon with n vertices. Since ChvataFs result, numerous variations on the art gallery problem have been studied, including mobile guards, guards with limited visibility or mobility, illumination of families of convex sets on the plane, guarding of rectilinear polygons, and others. In this paper, we survey most of these results.