A Combinatorial Bound for Beacon-based Routing in Orthogonal Polygons
Thomas Caton Shermer · Journal of Computational Geometry (Carleton University) · 2015
Beacon attraction is a movement system whereby a robot (modeled as a point in 2D) moves in a free space so as to always locally inimize its Euclidean distance to an activated beacon (which is also a point). This results in the robot moving directly towards the beacon when it can, and otherwise sliding along the edge of an obstacle. When a robot can reach the activated beacon by this method, we say that the beacon attracts the robot. A beacon routing from $p$ to $q$ is a sequence $b_1,b_2 ,\ldots,b_k$ of beacons such that activating the beacons in order will attract a robot from $p$ to $b_1$ to $b_2$ \ldots to $b_k$ to $q$ , where $q$ is considered to be a beacon. A routing set of beacons is a set $B$ of beacons such that any two points $p, q$ in the free space have a beacon routing with the intermediate beacons $b_1,b_2,\ldots,b_k$ all chosen from $B$ . Here we address the question of "how large must such a $B$ be?" in singly-connected orthogonal polygons, and show that the answer is "sometimes as large as $\left\lfloor\frac{n−4}{3}\right\rfloor$, but never larger."