Tight bounds for beacon-based coverage in simple rectilinear polygons

摘要

We establish tight bounds for beacon-based coverage problems. In particular, we show that [n/6] 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 [n+4/8]. We also present an optimal linear-time algorithm for computing the beacon kernel of P. (C) 2019 Elsevier B.V. All rights reserved.