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.
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 .
@cite_4 @cite_1 @cite_6 @cite_10 @cite_11
2105739218 2004151341 1816352825 1554447149
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. A 1.5-dimensional terrain T with n vertices is an xmonotone polygonal chain in the plane. A point guard p on T guards a point q of T if the line segment connecting p to q lies on or above T ; p is a vertex guard if it is a vertex of T . In the Optimal Terrain Guarding (OTG) problem on T , the objective is to guard the vertices of T by the minimum number of vertex guards. King and Krohn [9] showed that the OTG problem is NP-hard on arbitrary terrains, and [6] gave a PTAS for this problem. In this paper, we introduce directed visibility in which the visibility is directed only at adjacent vertices. We give an O(n)-time algorithm that solves the OTG problem exactly on orthogonal terrains under directed visibility. 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. 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. Computing a minimum vertex cover in graphs and hypergraphs is a well-studied optimizaton problem. While intractable in general, it is well known that on bipartite graphs, vertex cover is polynomial time solvable. In this work, we study the natural extension of bipartite vertex cover to hypergraphs, namely finding a small vertex cover in k- uniform k-partite hypergraphs, when the k-partition is given as input. For this problem Lovasz [16] gave a k 2 factor LP rounding based approximation, and a matching (k 2 - o(1)) integrality gap instance was constructed by [1]. We prove the following results, which are the first strong hardness results for this problem (heree > 0 is an arbitrary constant): - NP-hardness of approximating within a factor of (k 4 -e), and - Unique Games-hardness of approximating within a factor of (k 2 -e), showing optimality of Lovasz's algorithm under the Unique Games conjecture. The NP-hardness result is based on a reduction from minimum vertex cover in r-uniform hypergraphs for which NP-hardness of approximating within r-1-e was shown by [5]. The Unique Games-hardness result is obtained by applying the recent results of [15], with a slight modification, to the LP integrality gap due to [1]. The modification is to ensure that the reduction preserves the desired structural properties of the hypergraph.