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

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