TY - JOUR
T1 - Guarding Orthogonal Art Galleries with Sliding k-Transmitters
T2 - Hardness and Approximation
AU - Biedl, Therese
AU - Chan, Timothy M.
AU - Lee, Stephanie
AU - Mehrabi, Saeed
AU - Montecchiani, Fabrizio
AU - Vosoughpour, Hamideh
AU - Yu, Ziting
N1 - Funding Information:
A preliminary version of this paper appeared in proceedings of the 11th International Conference and Workshop on Algorithms and Computation (WALCOM 2017) [5] and the 28th Canadian Conference on Computational Geometry (CCCG 2016) [8]. Research of TB and TC is supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC). Research of FM is supported in part by the project: “Algoritmi e sistemi di analisi visuale di reti complesse e di grandi dimensioni” - Ricerca di Base 2017, Dipartimento di Ingegneria dell’Universit degli Studi di Perugia”. Research was done while FM was visiting the University of Waterloo.
Publisher Copyright:
© 2018, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2019/1/15
Y1 - 2019/1/15
N2 - A sliding k-transmitter inside an orthogonal polygon P, for a fixed k≥ 0 , is a point guard that travels along an axis-parallel line segment s in P. The sliding k-transmitter can see a point p∈ P if the perpendicular from p onto s intersects the boundary of P in at most k points. In the Minimum Sliding k-Transmitters (ST k) problem, the objective is to guard P with the minimum number of sliding k-transmitters. In this paper, we give a constant-factor approximation algorithm for the ST k problem on P for any fixed k≥ 0. Moreover, we show that the ST problem is NP-hard on orthogonal polygons with holes even if only horizontal sliding 0-transmitters are allowed. For k> 0 , the problem is NP-hard even in the extremely restricted case where P is simple and monotone. Finally, we study art gallery theorems; i.e., we give upper and lower bounds on the number of sliding transmitters required to guard P relative to the number of vertices of P.
AB - A sliding k-transmitter inside an orthogonal polygon P, for a fixed k≥ 0 , is a point guard that travels along an axis-parallel line segment s in P. The sliding k-transmitter can see a point p∈ P if the perpendicular from p onto s intersects the boundary of P in at most k points. In the Minimum Sliding k-Transmitters (ST k) problem, the objective is to guard P with the minimum number of sliding k-transmitters. In this paper, we give a constant-factor approximation algorithm for the ST k problem on P for any fixed k≥ 0. Moreover, we show that the ST problem is NP-hard on orthogonal polygons with holes even if only horizontal sliding 0-transmitters are allowed. For k> 0 , the problem is NP-hard even in the extremely restricted case where P is simple and monotone. Finally, we study art gallery theorems; i.e., we give upper and lower bounds on the number of sliding transmitters required to guard P relative to the number of vertices of P.
KW - Art gallery problem
KW - Sliding k-transmitters
KW - ϵ-nets
UR - http://www.scopus.com/inward/record.url?scp=85044285122&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85044285122&partnerID=8YFLogxK
U2 - 10.1007/s00453-018-0433-6
DO - 10.1007/s00453-018-0433-6
M3 - Article
AN - SCOPUS:85044285122
SN - 0178-4617
VL - 81
SP - 69
EP - 97
JO - Algorithmica (New York)
JF - Algorithmica (New York)
IS - 1
ER -