TY - GEN
T1 - Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons
AU - Bae, Sang Won
AU - Shin, Chan-Su
AU - Vigneron, Antoine E.
N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: Work by S.W.Bae was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (2013R1A1A1A05006927) and by the Ministry of Education (2015R1D1A1A01057220). Work by C.-S. Shin was supported by Research Grant of Hankuk University of Foreign Studies. Work by A. Vigneron was supported by KAUST base funding
PY - 2016/3/22
Y1 - 2016/3/22
N2 - We establish tight bounds for beacon-based coverage problems. In particular, we show that $\lfloor \frac{n}{6} \rfloor$ beacons are always sufficient and sometimes necessary to cover a simple rectilinear polygon P with n vertices. When P is monotone and rectilinear, we prove that this bound becomes $\lfloor \frac{n+4}{8} \rfloor$ . We also present an optimal linear-time algorithm for computing the beacon kernel of P.
AB - We establish tight bounds for beacon-based coverage problems. In particular, we show that $\lfloor \frac{n}{6} \rfloor$ beacons are always sufficient and sometimes necessary to cover a simple rectilinear polygon P with n vertices. When P is monotone and rectilinear, we prove that this bound becomes $\lfloor \frac{n+4}{8} \rfloor$ . We also present an optimal linear-time algorithm for computing the beacon kernel of P.
UR - http://hdl.handle.net/10754/622262
UR - http://link.springer.com/10.1007/978-3-662-49529-2_9
UR - http://www.scopus.com/inward/record.url?scp=84961718048&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-49529-2_9
DO - 10.1007/978-3-662-49529-2_9
M3 - Conference contribution
SN - 9783662495285
SP - 110
EP - 122
BT - LATIN 2016: Theoretical Informatics
PB - Springer Nature
ER -