Andre van Renssen

We present a deterministic local routing scheme that is guaranteed
to find a path between any pair of vertices in a half-θ_{6}-graph
whose length is at most 5/sqrt(3) times the Euclidean distance
between the pair of vertices. The half-θ_{6}-graph is identical to
the Delaunay triangulation where the empty region is an equilateral
triangle. 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 because the spanning ratio of the
half-θ_{6}-graph is 2. Since every triangulation can be embedded in the
plane as a half-θ_{6}-graph using *O*(log *n*) bits per vertex coordinate
via Schnyder's embedding scheme (SODA 1990), our result provides a
competitive local routing scheme for every such embedded triangulation.