On a Family of Strong Geometric Spanners That Admit Local Routing Strategies

摘要

We introduce a family of directed geometric graphs, denoted G~θ_λ, that depend on two parameters λ and θ. For 0≤θ ＜π/2 and 1/2 ＜λ＜1 , the G~θ_λ graph is a strong t-spanner, with t=1/((1-λ)∝θ) .^sThe out-degree of a node in the G~θ_λ graph is at most [2π/min(θ,arccos1/2λ] . Moreover, we show that routing can be achieved locally on G~θ_λ . Next, we show that all strong t-spanners are also t-spanners of the unit disk graph. Simulations for various values of the parameters λ and θ indicate that for random point sets, the spanning ratio of is better than the proven theoretical bounds.