**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

### Geometry and Topology Seminar

# Routing Among Obstacles

### Andre van Renssen (Sydney)

Please join us for lunch at 1 p.m.
**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.