A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras

DOI10.1007/978-3-319-19315-1_13zbMath1401.68349arXiv1308.2757OpenAlexW973397369MaRDI QIDQ2946049

Saeed Mehrabi, Stephane Durocher, Ali D. Mehrabi, Robert Fraser, Omrit Filtser

Publication date: 15 September 2015

Published in: Lecture Notes in Computer Science, LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1308.2757

Mathematics Subject Classification ID

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

Related Items

Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ On orthogonally guarding orthogonal polygons with bounded treewidth ⋮ A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras ⋮ On Guarding Orthogonal Polygons with Sliding Cameras ⋮ Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation ⋮ Covering orthogonal polygons with sliding \(k\)-transmitters ⋮ Parameter analysis for guarding terrains

Cites Work

• The art gallery theorem for polyominoes
• Cooperative mobile guards in grids
• Covering orthogonal polygons with star polygons: The perfect graph approach
• Approximation algorithms for art gallery problems in polygons
• Covering grids and orthogonal polygons with periscope guards
• Approximate guarding of monotone and rectilinear polygons
• Guarding Orthogonal Art Galleries Using Sliding Cameras: Algorithmic and Hardness Results
• A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras
• GUARDING ORTHOGONAL ART GALLERIES WITH SLIDING CAMERAS
• POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
• Computational complexity of art gallery problems
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
• An Efficient Algorithm for Mobile Guarded Guards in Simple Grids
• Unnamed Item
• Unnamed Item
• Unnamed Item