Competitive Online Routing on Delaunay Triangulations.

Let be a graph, be a source node and be a target node. The sequence of adjacent nodes (graph walk) visited by a routing algorithm is a -competitive route if its length in is at most times the length of the shortest path from to in . We present a -competitive online routing algorithm on the Delaunay triangulation of an arbitrary given set of points in the plane. This improves the competitive ratio on Delaunay triangulations from the previous best of . We also present a -competitive online routing algorithm for Delaunay triangulations of point sets in convex position. [ABSTRACT FROM AUTHOR]