SMS scnews item created by Boris Lishak at Thu 6 Sep 2018 1122
Type: Seminar
Distribution: World
Calendar1: 12 Sep 2018 1200-1300
CalLoc1: Carslaw 535A
CalTitle1: van Renssen -- Routing Among Obstacles
Auth: borisl@dora.maths.usyd.edu.au

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

Actions: