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

Abstract

We introduce a family of directed geometric graphs, denoted $G_\lambda^\theta$, that depend on two parameters λ and θ. For $0\leq \theta<\frac{\pi}{2}$ and $\frac{1}{2} < \lambda < 1$, the $G_\lambda^\theta$ graph is a strong t-spanner, with $t=\frac{1}{(1-\lambda)\cos\theta}$. The out-degree of a node in the $G_\lambda^\theta$ graph is at most $\lfloor2\pi/\min(\theta, \arccos\frac{1}{2\lambda})\rfloor$. Moreover, we show that routing can be achieved locally on $G_\lambda^\theta$. 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 $G_\lambda^\theta$ is better than the proven theoretical bounds.

Research supported in part by NSERC, MITACS, MRI, and HPCVL.