Improved Approximations for Guarding 1.5-Dimensional Terrains

K. Elbassioni, D. Matijevic, J. Mestre +1

We present a 4-approximation algorithm for the problem of placing a fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves…