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

2 Scopus citations

Abstract

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
Pages110-122
Number of pages13
ISBN (Print)9783662495285
DOIs
StatePublished - Mar 22 2016

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

Cite this