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.
展开▼
