An Approximation Scheme for Terrain Guarding Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
edited by: Irit Dinur, Klaus Jansen, Joseph Naor, José Rolim
We obtain a polynomial time approximation scheme for the terrain guarding problem improving upon several recent constant factor approximations. Our algorithm is a local search algorithm inspired by the recent results of Chan and Har-Peled  and Mustafa and Ray . Our key contribution is to show the existence of a planar graph that appropriately relates the local and global optimum.