2011-08-01
On a family of strong geometric spanners that admit local routing strategies
Publication
Publication
Computational Geometry , Volume 44 - Issue 6-7 p. 319- 328
We introduce a family of directed geometric graphs, whose vertices are points in Rd. The graphs Gλθ in this family depend on two real parameters λ and θ. For 12<λ<1 and π3<θ<π2, the graph Gλθ is a strong t-spanner for t=1(1-λ)cosθ. That is, for any two vertices p and q, Gλθ contains a path from p to q of length at most t times the Euclidean distance |pq|, and all edges on this path have length at most |pq|. The out-degree of any node in the graph Gλθ is O(1/πd- 1), where π=min(θ,arccos12λ). We show that routing on Gλθ can be achieved locally. Finally, we show that all strong t-spanners are also t-spanners of the unit-disk graph.
Additional Metadata | |
---|---|
, , | |
doi.org/10.1016/j.comgeo.2011.01.002 | |
Computational Geometry | |
Organisation | School of Computer Science |
Bose, P, Carmi, P. (Paz), Couture, M. (Mathieu), Smid, M, & Xu, D. (Daming). (2011). On a family of strong geometric spanners that admit local routing strategies. Computational Geometry, 44(6-7), 319–328. doi:10.1016/j.comgeo.2011.01.002
|