Competitive routing on a bounded-degree plane spanner
We show that it is possible to route locally and com- petitively on two bounded-degree plane 6-spanners, one with maximum degree 12 and the other with maximum degree 9. Both spanners are subgraphs of the empty equilateral triangle Delaunay triangulation. First, in a weak routing model where the only information stored at each vertex is its neighbourhood, we show how to find a path between any two vertices of a 6-spanner of max- imum degree 12, such that the path has length at most 95/√ 3 times the straight-line distance between the ver- Tices. In a slightly stronger model, where in addition to the neighbourhood of each vertex, we store O(1) addi- Tional information, we show how to find a path that has length at most 15/√ 3 times the Euclidean distance both in a 6-spanner of maximum degree 12 and a 6-spanner of maximum degree 9.
|Conference||24th Canadian Conference on Computational Geometry, CCCG 2012|
Bose, P, Fagerberg, R. (Rolf), Van Renssen, A. (André), & Ver Don Schot, S. (Sander). (2012). Competitive routing on a bounded-degree plane spanner. Presented at the 24th Canadian Conference on Computational Geometry, CCCG 2012.