Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation
DOI10.1007/s00453-018-0433-6zbMath1410.68365OpenAlexW2790698188MaRDI QIDQ1755780
Fabrizio Montecchiani, Timothy M. Chan, Hamideh Vosoughpour, Ziting Yu, Saeed Mehrabi, Stephanie Tien Lee, Therese C. Biedl
Publication date: 11 January 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-018-0433-6
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (2)
Cites Work
- Orthogonal segment stabbing
- An alternative proof of the rectilinear art gallery theorem
- Improved approximation algorithms for geometric set cover
- Galleries need fewer mobile guards: A variation on Chvatal's theorem
- A unified approach to visibility representations of planar graphs
- On triangulating planar graphs under the four-connectivity constraint
- A combinatorial theorem in plane geometry
- Combinatorics and complexity of guarding polygons with edge and point 2-transmitters
- Modem illumination of monotone polygons
- Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation
- Almost optimal set covers in finite VC-dimension
- Coverage with \(k\)-transmitters in the presence of obstacles
- An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
- Guarding monotone art galleries with sliding cameras in linear time
- Approximate guarding of monotone and rectilinear polygons
- Guarding orthogonal art galleries with sliding cameras
- Guarding Thin Orthogonal Polygons Is Hard
- Guarding Orthogonal Art Galleries Using Sliding Cameras: Algorithmic and Hardness Results
- 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 CAMERAS
- Traditional Galleries Require Fewer Watchmen
- Computational complexity of art gallery problems
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
- Inapproximability results for guarding polygons and terrains
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation
