Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414752 | Computational Geometry | 2011 | 10 Pages |
Abstract
We introduce a family of directed geometric graphs, whose vertices are points in Rd. The graphs in this family depend on two real parameters λ and θ. For and , the graph is a strong t-spanner for . That is, for any two vertices p and q, contains a path from p to q of length at most t times the Euclidean distance |pq|, and all edges on this path have length at most |pq|. The out-degree of any node in the graph is O(1/ϕd−1), where . We show that routing on can be achieved locally. Finally, we show that all strong t-spanners are also t-spanners of the unit-disk graph.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics