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.
|Titel||Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms|
|Status||Udgivet - 2012|
|Begivenhed||The Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms - Kyoto, Japan|
Varighed: 17. jan. 2012 → 19. jan. 2012
|Konference||The Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms|
|Periode||17/01/2012 → 19/01/2012|