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

DOI10.1016/j.comgeo.2017.06.004zbMath1385.65023arXiv1503.05681OpenAlexW104118994MaRDI 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-hardnessart gallery problem\(k\)-transmitter2-transmitter

Mathematics Subject Classification ID

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

Related Items (4)

Guarding monotone art galleries with sliding cameras in linear time ⋮ \(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

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

This page was built for publication: Combinatorics and complexity of guarding polygons with edge and point 2-transmitters