Improved Approximation for Guarding Simple Galleries from the Perimeter

James King, David Kirkpatrick

We provide an O(log log OPT)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for buil…