Local Routing on Delaunay Triangulations
Darryl Hill
Carleton University

We will look at local routing on geometric graphs. Let $G$ be a geometric graph on a point set $P$. For two vertices $s$ and $t$ in $P$, we are interested in routing a packet through $G$ from $s$ to $t$ using local knowledge and constant memory, such that the length of the path found is not more than a constant $c$ times the Euclidean distance between $s$ and $t$. The constant $c$ is known as the routing ratio.

While the problem is not solvable in arbitrary graphs, there are classes of graphs on which it can be solved. We will look specifically at the Delaunay triangulation. The current best routing algorithm on the Delaunay triangulation achieves a routing ratio of $5.9$. We will describe, in high level, three routing algorithms that we are currently working on that look to improve this bound. We will give a flavour of the analysis, and the relative strengths and weaknesses of each algorithm.