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_4: 
  @cite_1: We present the first constant-factor approximation algorithm for a nontrivial instance of the optimal guarding (coverage) problem in polygons. In particular, we give an @math -approximation algorithm for placing the fewest point guards on a 1.5D terrain, so that every point of the terrain is seen by at least one guard. While polylogarithmic-factor approximations follow from set cover results, our new results exploit the geometric structure of terrains to obtain a substantially improved approximation algorithm.
  @cite_6: 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.
  @cite_10: We obtain a polynomial time approximation scheme for the terrain guarding problem improving upon several recent constant factor approximations. Our algorithm is a local search algorithm inspired by the recent results of Chan and Har-Peled [2] and Mustafa and Ray [15]. Our key contribution is to show the existence of a planar graph that appropriately relates the local and global optimum.
  @cite_11: In the continuous 1.5-dimensional terrain guarding problem we are given an x-monotone chain (the terrain T ) and ask for the minimum number of point guards (located anywhere on T ), such that all points of T are covered by at least one guard. It has been shown that the 1.5-dimensional terrain guarding problem is NPhard. The currently best known approximation algorithm achieves a factor of 4. For the discrete problem version with a nite set of guard candidates and a nite set of points on the terrain that need to be monitored, a polynomial time approximation scheme (PTAS) has been presented [11]. We show that for the general problem we can construct nite guard and witness sets, G and W , such that there exists an optimal guard cover G G that covers T , and when these guards monitor all points in W the entire terrain is guarded. This leads to a PTAS as well as an (exact) IP formulation for the continuous terrain guarding problem.
summary: Terrain Guarding Problem for general 1.5D terrains is shown to be NP-hard by a reduction from @cite_6 . Ben-Moshe . @cite_1 gave the first @math -approximation algorithm. Elbassioni . @cite_4 gave an improvement by showing that LP rounding results in a 4-approximation for TGP @math if @math (a 5-approximation otherwise). A local search based PTAS is also proposed for TGP @cite_11 @cite_10 .