Competitive routing in the half-θ 6-graph
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/√3 = 2.886... 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. Copyright
|Conference||23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012|
Bose, P, Fagerberg, R. (Rolf), Van Renssen, A. (André), & Verdonschot, S. (Sander). (2012). Competitive routing in the half-θ 6-graph. Presented at the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012.