Improved approximation for guarding simple galleries from the perimeter (Q635755): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
 
(2 intermediate revisions by 2 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/s00454-011-9352-x / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2139332235 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learnability and the Vapnik-Chervonenkis dimension / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient visibility queries in simple polygons / rank
 
Normal rank
Property / cites work
 
Property / cites work: Almost optimal set covers in finite VC-dimension / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Greedy Heuristic for the Set-Covering Problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Guarding galleries and terrains / rank
 
Normal rank
Property / cites work
 
Property / cites work: Inapproximability results for guarding polygons and terrains / rank
 
Normal rank
Property / cites work
 
Property / cites work: A threshold of ln <i>n</i> for approximating set cover / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198056 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Guarding galleries where every point sees a large area / rank
 
Normal rank
Property / cites work
 
Property / cites work: Almost tight bounds for \(\epsilon\)-nets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Computational complexity of art gallery problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3799261 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some NP-hard polygon decomposition problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4527015 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Guarding galleries where no point sees a small area. / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities / rank
 
Normal rank

Latest revision as of 10:37, 4 July 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
    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
    0 references
    0 references
    0 references
    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
    0 references