On a family of strong geometric spanners that admit local routing strategies
| dc.creator | Bose, Prosenjit | |
| dc.creator | Carmi, Paz | |
| dc.creator | Couture, Mathieu | |
| dc.creator | Smid, Michiel | |
| dc.creator | Xu, Daming | |
| dc.date | 2007-02-20 | |
| dc.date | 2007-02-22 | |
| dc.date.accessioned | 2026-07-07T07:48:08Z | |
| dc.date.available | 2026-07-07T07:48:08Z | |
| dc.description | We introduce a family of directed geometric graphs, denoted $\paz$, that depend on two parameters $λ$ and $θ$. For $0\leq θ<\fracπ{2}$ and ${1/2} < λ< 1$, the $\paz$ graph is a strong $t$-spanner, with $t=\frac{1}{(1-λ)\cosθ}$. The out-degree of a node in the $\paz$ graph is at most $\lfloor2π/\min(θ, \arccos\frac{1}{2λ})\rfloor$. Moreover, we show that routing can be achieved locally on $\paz$. 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 $\paz$ is better than the proven theoretical bounds. | |
| dc.identifier | https://arxiv.org/abs/cs/0702117 | |
| dc.identifier | http://arxiv.org/abs/cs/0702117 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/124391 | |
| dc.subject | Computational Geometry | |
| dc.title | On a family of strong geometric spanners that admit local routing strategies | |
| dc.type | text |