text: 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.
  @cite_7: Polygon partitions Orthogonal polygons Mobile guards Miscellaneous shapes Holes Exterior visibility Visibility groups Visibility algorithms Minimal guard covers Three-dimensions and miscellany.
  @cite_3: We show that vertex guarding a monotone polygon is NP-hard and construct a constant factor approximation algorithm for interior guarding monotone polygons. Using this algorithm we obtain an approximation algorithm for interior guarding rectilinear polygons that has an approximation factor independent of the number of vertices of the polygon. If the size of the smallest interior guard cover is OPT for a rectilinear polygon, our algorithm produces a guard set of size O(OPT 2).
  @cite_0: D. T. Lee and A. K. Lin [2] proved that VERTEX-GUARDING and POINT-GUARDING are NP-hard for simple polygons. We prove that those problems are NP-hard for ortho-polygons, too.
  @cite_2: 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.
  @cite_12: 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.
summary: 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 .