Improved approximation for guarding simple galleries from the perimeter (Q635755): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 09:19, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Improved approximation for guarding simple galleries from the perimeter |
scientific article |
Statements
Improved approximation for guarding simple galleries from the perimeter (English)
0 references
23 August 2011
0 references
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.
0 references
art gallery problem
0 references
polygon guarding
0 references
approximation algorithm
0 references
epsilon-nets
0 references
perimeter guards
0 references
vertex guards
0 references