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)

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