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

zbMATH Keywords

art gallery problem\(\epsilon \)-netssliding \(k\)-transmitters

Mathematics Subject Classification ID

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)

\(k\)-Transmitter watchman routes ⋮ Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation