Optimal local routing on Delaunay triangulations defined by empty equilateral triangles

Abstract

We present a deterministic local routing algorithm that is guaranteed to find a path between any pair of vertices in a half-$\hat{I}{¸}_6$-graph (the half-$\hat{I}{¸}_6$-graph is equivalent to the Delaunay triangulation where the empty region is an equilateral triangle). The length of the path is at most $5/\sqrt{3}\approx 2.887$ times the Euclidean distance between the pair of vertices. Moreover, we show that no local routing algorithm can achieve a better routing ratio, thereby proving that our routing algorithm is optimal. This is somewhat surprising because the spanning ratio of the half-$\hat{I}{¸}_6$-graph is 2, meaning that even though there always exists a path whose lengths is at most twice the Euclidean distance, we cannot always find such a path when routing locally. Since every triangulation can be embedded in the plane as a half-$\hat{I}{¸}_6$-graph using $O(\log n)$ bits per vertex coordinate via Schnyder's embedding scheme (SODA 1990), our result provides a competitive local routing algorithm for every such embedded triangulation. Finally, we show how our routing algorithm can be adapted to provide a routing ratio of $15/\sqrt{3}\approx 8.660$ on two bounded degree subgraphs of the half-$\hat{I}{¸}_6$-graph.

26 pages, 18 figures. Journal version of results presented at SODA 2012 and CCCG 2012