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 -