A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
DOI10.1007/978-3-540-73951-7_15zbMATH Open1209.68582DBLPconf/wads/DeshpandeKDS07OpenAlexW2048740780WikidataQ56504465 ScholiaQ56504465MaRDI QIDQ3603524FDOQ3603524
Authors: Ajay Deshpande, Taejung Kim, Erik D. Demaine, Sanjay E. Sarma 
Publication date: 17 February 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-73951-7_15
Recommendations
- An approximation algorithm for the art gallery problem
- Approximation algorithms for art gallery problems in polygons
- An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
- Approximability of guarding weak visibility polygons
- Improved approximation for guarding simple galleries from the perimeter
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cited In (16)
- Improved approximation for guarding simple galleries from the perimeter
- Guarding Art Galleries: The Extra Cost for Sculptures Is Linear
- A constant-factor approximation algorithm for vertex guarding a WV-polygon
- Approximation algorithms for art gallery problems in polygons
- Approximability of guarding weak visibility polygons
- The VC-dimension of visibility on the boundary of monotone polygons
- Line segment visibility with sidedness constraints
- How to Keep an Eye on Small Things
- An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
- Approximate guarding of monotone and rectilinear polygons
- A Novel Efficient Approach for Solving the Art Gallery Problem
- The parameterized complexity of guarding almost convex polygons
- A nearly optimal algorithm for covering the interior of an art gallery
- Parameterized Analysis of Art Gallery and Terrain Guarding
- Title not available (Why is that?)
- An approximation algorithm for the art gallery problem
This page was built for publication: A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3603524)
