Improved Routing on the Delaunay Triangulation

Darryl Hill

Carleton University

A geometric graph $G=(P,E)$ is a set of points $P$ in the plane and a set $E$ of edges between pairs of points, where the weight of an edge is equal to the Euclidean distance between its two endpoints. In local routing we find a path in $G$ from a source vertex $s$ to a destination vertex $t$, using only knowledge of the current vertex, the location of the neighbours of the current vertex, and the locations of $s$ and $t$. We present an algorithm for local routing on the Delaunay triangulation, and show that it finds a path between a source vertex $s$ and a target vertex $t$ that is not longer than $3.56|st|$, improving the previous bound of $5.9|st|$.