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 finite set of guard candidates and a finite 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 finite 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.
Friedrichs et al. REF revealed that for the continuous 1.5D terrain guarding problem, finite guard and witness sets (G and X, respectively) can be constructed such that an optimal guard cover G ⊆ G that covers terrain T is present and when these guards monitor all points in X, the entire terrain is guarded.
A PTAS for the continuous 1.5D Terrain Guarding Problem
ArXiv
ArXiv
Mathematics Computer Science