Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6868475 | Computational Geometry | 2018 | 12 Pages |
Abstract
We consider a generalization of the classical Art Gallery Problem, where instead of a light source, the guards, called k-transmitters, model a wireless device with a signal that can pass through at most k walls. We show it is NP-hard to compute a minimum cover of point 2-transmitters, point k-transmitters, and edge 2-transmitters in a simple polygon. The point 2-transmitter result extends to orthogonal polygons. In addition, we give necessity and sufficiency results for the number of edge 2-transmitters in general, monotone, orthogonal monotone, and orthogonal polygons.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sarah Cannon, Thomas G. Fai, Justin Iwerks, Undine Leopold, Christiane Schmidt,