Improved approximation for guarding simple galleries from the perimeter (Q635755): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:49, 5 March 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