Improved Bounds for Beacon-Based Coverage and Routing in Simple Rectilinear Polygons

Abstract

We establish tight bounds for beacon-based coverage problems, and improve the bounds for beacon-based routing problems in simple rectilinear polygons. Specifically, 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. We also prove tight bounds for the case where $P$ is monotone, and we present an optimal linear-time algorithm that computes the beacon-based kernel of $P$. For the routing problem, we show that $\lfloor \frac{3n-4}{8}\rfloor -1$ beacons are always sufficient, and $\lceil \frac{n}{4}\rceil -1$ beacons are sometimes necessary to route between all pairs of points in $P$.

23 pages, 15 figures