Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons

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

doi:10.1007/978-3-662-49529-2_9

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 proceeding › Conference contribution

3 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 language	English (US)
Title of host publication	LATIN 2016: Theoretical Informatics
Publisher	Springer Nature
Pages	110-122
Number of pages	13
ISBN (Print)	9783662495285
DOIs	https://doi.org/10.1007/978-3-662-49529-2_9
State	Published - 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

Access to Document

10.1007/978-3-662-49529-2_9

Cite this

@inproceedings{8fd2e796a10644779fbf8c6cb08bc6c8,

title = "Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons",

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.",

author = "Bae, {Sang Won} and Chan-Su Shin and Vigneron, {Antoine E.}",

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",

year = "2016",

month = mar,

day = "22",

doi = "10.1007/978-3-662-49529-2_9",

language = "English (US)",

isbn = "9783662495285",

pages = "110--122",

booktitle = "LATIN 2016: Theoretical Informatics",

publisher = "Springer Nature",

}

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 -

Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this