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

DOI10.1007/978-3-540-73951-7_15MaRDI QIDQ3603524zbMATH OpenOpenAlexDBLPWikidataFDO

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

Mathematics Subject Classification ID

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

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

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
• scientific article; zbMATH DE number 7236415 (Why is no real title available?)
• 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)