# Competitive Online Routing on Delaunay Triangulations

Prosenjit Bose,
Jean-Lou De Carufel,
Stephane Durocher,
Perouz Taslakian

January 2014

### Abstract

Let $G$ be a graph, $s ın G$ be a source node and $t ın G$ 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.

Publication

*Algorithm Theory – 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT14)*