Routing on the Visibility Graph
Prosenjit K. Bose, Matias Korman, Sander Verdonschot, André van Renssen · Journal of Computational Geometry (Carleton University) · 2017
We consider the problem of routing on a network in the presence of line segment constraints (i.e., obstacles that edges in our network are not allowed to cross). Let $P$ be a set of $n$ points in the plane and let $S$ be a set of non-crossing line segments whose endpoints are in $P$. We present two deterministic 1-local $O(1)$-memory routing algorithms (i.e., the algorithms never look beyond the direct neighbours of the current location and store only a constant amount of additional information). These algorithms are guaranteed to find a path consisting of at most a linear number of edges between any pair of vertices of the visibility graph of $P$ subject to a set of constraints $S$. Contrary to all existing deterministic local routing algorithms, our routing algorithms do not route on a plane subgraph of the visibility graph. Additionally, we provide lower bounds on the routing ratio of any deterministic local routing algorithm on the visibility graph.