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

Abstrakt

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

Konference

KonferenceThe Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms
Land/OmrådeJapan
ByKyoto
Periode17/01/201219/01/2012

Fingeraftryk

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

Citationsformater