Routing Among Obstacles

Andre van Renssen (Sydney)

Abstract

Joint work with: Prosenjit Bose, Rolf Fagerberg, Matias Korman, Sander Verdonschot

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).

The first is 2-competitive, but only works between visible pairs of vertices. The second works between any pair of vertices, but is no longer competitive. Instead, we show that it reaches the destination using at most a linear number of edges. Additionally, we show that no deterministic local routing algorithm can be competitive on all pairs of vertices.