Title: Competitive Routing on a Variant of the Delaunay Triangulation

Abstract: A subgraph H of a weighted graph G is a t-spanner of G provided that for every edge xy in G, the weight of the shortest path between x and y in H is at most t times the weight of xy. It is known that the Delaunay triangulation of a point set P (where the empty region is an equilateral triangle) is a 2-spanner of the complete Euclidean graph. We present a new and simple proof of this spanning ratio that allows us to route competitively on this graph. Specifically, we present a deterministic local routing scheme that is guaranteed to find a short path between any pair of vertices in this Delaunay triangulation. We guarantee that the length of the path is at most 5/sqrt(3) times the Euclidean distance between the pair of vertices. Moreover, we show that no local routing scheme can achieve a better competitive spanning ratio thereby implying that our routing scheme is optimal. This is somewhat surprising since the spanning ratio is 2.