A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
Boaz Ben Moshe, Matthew J. Katz, Joseph S. B. Mitchell · SIAM Journal on Computing · 2007
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 $O(1)$‐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.