Competitive Online Routing on Delaunay Triangulations

Abstract

Let $G$ be a graph, $sınG$ be a source node and $tınG$ be a target node. The sequence of adjacent nodes (graph walk) visited by a routing algorithm is a $c$-competitive route if its length in $G$ is at most $c$ times the length of the shortest path from $s$ to $t$ in $G$. We present a 15.479-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 45.749. We also present a 7.621-competitive online routing algorithm for Delaunay triangulations of point sets in convex position.