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

The authors 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−¦Ë) cos¦È. The out-degree of a node in the G¦È¦Ë graph is at most ⌊2¦Ð/min(¦È, arccos 1/2 ¦Ë)⌋. Moreover, they show that routing can be achieved locally on G¦È¦Ë. Next, they 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¦È¦Ë is better than the proven theoretical bounds.