On Guarding Orthogonal Polygons with Sliding Cameras

DOI10.1007/978-3-319-53925-6_5zbMath1485.68262arXiv1604.07099OpenAlexW2962749981MaRDI QIDQ2980898

Fabrizio Montecchiani, Saeed Mehrabi, Hamideh Vosoughpour, Timothy M. Chan, Stephanie Tien Lee, Therese C. Biedl

Publication date: 5 May 2017

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Guarding monotone art galleries with sliding cameras in linear time, On orthogonally guarding orthogonal polygons with bounded treewidth, Mobile versus point guards, Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation

Cites Work

• Unnamed Item
• Orthogonal segment stabbing
• Improved approximation algorithms for geometric set cover
• A unified approach to visibility representations of planar graphs
• A combinatorial theorem in plane geometry
• Almost optimal set covers in finite VC-dimension
• An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
• Approximate guarding of monotone and rectilinear polygons
• On guarding the vertices of rectilinear domains
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Guarding Thin Orthogonal Polygons Is Hard
• Guarding Orthogonal Art Galleries Using Sliding Cameras: Algorithmic and Hardness Results
• Guarding Monotone Art Galleries with Sliding Cameras in Linear Time
• A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras
• GUARDING ORTHOGONAL ART GALLERIES WITH SLIDING CAMERAS
• Traditional Galleries Require Fewer Watchmen
• Computational complexity of art gallery problems
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Approximation algorithms for NP-complete problems on planar graphs
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
• Parameterized Algorithms
• Inapproximability results for guarding polygons and terrains