Improved approximation for guarding simple galleries from the perimeter (Q635755)

In this paper, the authors present an \(O(\log \log \text{OPT})\)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. The running time of this algorithm is polynomial in the number of vertices \(n\) of the polygon and the number of potential guard locations. If the set of potential guard locations is infinite, then the authors use the discretization technique of \textit{A. Deshpande}, \textit{T. Kim}, \textit{E. D. Demaine} and \textit{S. E. Sarma} [Lect. Notes Comput. Sci. 4619, 163--174 (2007; Zbl 1209.68582)]. Their algorithm is polynomial in \(n\) and \(\Delta\), where \(\Delta\) is the ratio between the longest and the shortest distances between vertices.