A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems

DOI10.1007/978-3-540-73951-7_15zbMath1209.68582DBLPconf/wads/DeshpandeKDS07OpenAlexW2048740780WikidataQ56504465 ScholiaQ56504465MaRDI QIDQ3603524

Ajay Deshpande, Erik D. Demaine, Taejung Kim, 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

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (12)

Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ The VC-dimension of visibility on the boundary of monotone polygons ⋮ Approximate guarding of monotone and rectilinear polygons ⋮ Line segment visibility with sidedness constraints ⋮ Guarding Art Galleries: The Extra Cost for Sculptures Is Linear ⋮ The parameterized complexity of guarding almost convex polygons ⋮ Improved approximation for guarding simple galleries from the perimeter ⋮ Unnamed Item ⋮ An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries ⋮ How to Keep an Eye on Small Things ⋮ A constant-factor approximation algorithm for vertex guarding a WV-polygon ⋮ Approximability of guarding weak visibility polygons

This page was built for publication: A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems