2015-01-01

# Optimal local routing on Delaunay triangulations defined by empty equilateral triangles

## Publication

### Publication

*SIAM Journal on Computing , Volume 44 - Issue 6 p. 1626- 1649*

We present a deterministic local routing algorithm that is guaranteed to find a path between any pair of vertices in a half-$\theta_6$-graph (the half-$\theta_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-$\theta_6$-graph is 2, meaning that even though there always exists a path whose length 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-$\theta_6$-graph using $O(\log n)$ bits per vertex coordinate via Schnyder's embedding scheme [W. Schnyder, Embedding planar graphs on the grid, in Proceedings of the 1st Annual ACM--SIAM Symposium on Discrete Algorithms (SODA 1990), ACM, New York, SIAM, Philadelphia, 1990, pp. 138--148], 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-$\theta_6$-graph.

Additional Metadata | |
---|---|

Keywords | Competitive routing, Geometric spanner, Local routing, Online routing, Theta-graph |

Persistent URL | dx.doi.org/10.1137/140988103 |

Journal | SIAM Journal on Computing |

Citation |
Bose, P, Fagerberg, R. (Rolf), Van Renssen, A. (André), & Verdonschot, S. (Sander). (2015). Optimal local routing on Delaunay triangulations defined by empty equilateral triangles.
SIAM Journal on Computing, 44(6), 1626–1649. doi:10.1137/140988103 |