A constant-factor approximation algorithm for optimal terrain guarding
Boaz Ben Moshe, Matthew J. Katz, Joseph S. B. Mitchell · 2005
Abstract We present the first constant-factor approximation algorithm for a non-trivial instance of theoptimal guarding (coverage) problem in polygons. In particular, we give an O(1)-approximationalgorithm 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 fromset cover results, our new results exploit geometric structure of terrains to obtain a substantially improved approximation algorithm.