Competitive routing in the half-theta_6-graph

Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot

Publikation: Kapitel i bog/rapport/konference-proceedingKapitel i bogForskningpeer review


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.
TitelProceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms
StatusUdgivet - 2012
BegivenhedThe Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms - Kyoto, Japan
Varighed: 17. jan. 201219. jan. 2012


KonferenceThe Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms


Dyk ned i forskningsemnerne om 'Competitive routing in the half-theta_6-graph'. Sammen danner de et unikt fingeraftryk.