Combinatorics and complexity of guarding polygons with edge and point 2-transmitters

DOI10.1016/j.comgeo.2017.06.004zbMath1385.65023arXiv1503.05681MaRDI QIDQ1699283

Christiane Schmidt, Undine Leopold, Justin Iwerks, Thomas G. Fai, Sarah M. Cannon

Publication date: 19 February 2018

Published in: Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

NP-hardness; art gallery problem; \(k\)-transmitter; 2-transmitter

Mathematics Subject Classification ID

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

Related Items

\(k\)-Transmitter watchman routes, Guarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximation, Computing the \(k\)-visibility region of a point in a polygon, Guarding monotone art galleries with sliding cameras in linear time

Cites Work

• Unnamed Item
• Recognizing polygons, or how to spy
• A short proof of Chvatal's Watchman Theorem
• Edge guards in rectilinear polygons
• A combinatorial theorem in plane geometry
• Coverage with k-Transmitters in the Presence of Obstacles
• Traditional Galleries Require Fewer Watchmen
• Computational complexity of art gallery problems
• Some NP-hard polygon decomposition problems
• Polygons Have Ears
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
• Guarding polyominoes