Carleton University
Technical Report TR-07-08
March 1, 2007
On a Family of Strong Geometric Spanners that Admit Local Routing Strategies
Prosenjit Bose, Paz Carmi, Mathieu Couture, Michiel Smid, Daming Xu
Abstract
We introduce a family of directed geometric graphs, denoted G(lambda,theta), that depend on two parameters lambda and theta. For 0 <= theta < pi/2 and 1/2 < lambda < 1, the G(lambda,theta) graph is a strong t-spanner, with t=1/((1-lambda)cos(theta)). The out-degree of a node in the G(lambda,theta) graph is at most floor(2pi/(min(theta, arccos(1/2lambda))). 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 lambda and theta indicate that for random point sets, the spanning ratio of G(lambda,theta) is better than the proven theoretical bounds.