A constant-factor approximation algorithm for optimal 1.5D terrain guarding

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 geometrie structure of terrains to obtain a substantially improved approximation algorithm.