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.