Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons

Sang Won Bae, Chan-Su Shin, Antoine E. Vigneron

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


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.
Original languageEnglish (US)
Title of host publicationLATIN 2016: Theoretical Informatics
PublisherSpringer Nature
Number of pages13
ISBN (Print)9783662495285
StatePublished - Mar 22 2016

Bibliographical note

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


Dive into the research topics of 'Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons'. Together they form a unique fingerprint.

Cite this