On k-Guarding Polygons.
Daniel Busto, William Evans, David G. Kirkpatrick · 2013
We describe a polynomial time O(k log log OPTk(P))-approximation algorithm for the k-guarding problem of finding a minimum number, OPTk(P), of vertex guards of an n-vertex simple polygon P so that for every point p ∈ P, the number of guards that see p is at least the minimum of k and the number of vertices that see p. Our approach finds O k