Online Routing on Delaunay Triangulations

A routing algorithm on a geometric graph $G$ has a routing ratio of $c$ if the length of the path produced by the algorithm from any vertex $s$ to any vertex $t$ is at most $c$ times the length of the line segment $st$. The routing algorithm is online if it makes forwarding decisions based on

  1. the $k$-neighborhood in $G$ (for some integer constant $k > 0$) of the current position of the message and
  2. limited information stored in the header of the message.

We present an online routing algorithm on the Delaunay triangulation with routing ratio less than $5.90$. This improves upon the algorithm with best known routing ratio of $15.48$. The algorithm makes forwarding decisions based on the $1$-neighborhood of the current position of the message and the positions of the message source and destination only.