Routing on the visibility graph
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 that are guaranteed to find a path of at most linear size between any pair of vertices of the visibility graph of P with respect to a set of constraints S (i.e., the algorithms never look beyond the direct neighbours of the current location and store only a constant amount of information). Contrary to all existing deterministic local routing algorithms, our routing algorithms do not route on a plane subgraph of the visibility graph.
|Keywords||Constraints, Routing, Visibility graph, Θ-graph|
|Conference||28th International Symposium on Algorithms and Computation, ISAAC 2017|
Bose, P, Korman, M. (Matias), Vanrenssen, A. (André), & Verdonschot, S. (Sander). (2017). Routing on the visibility graph. In Leibniz International Proceedings in Informatics, LIPIcs. doi:10.4230/LIPIcs.ISAAC.2017.18