A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras
From MaRDI portal
Publication:2946049
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
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