Name
Abstract | ||
|---|---|---|
In greedy geometric routing, messages are passed in a network embedded in a metric space according to the greedy strategy of always forwarding messages to nodes that are closer to the destination. In this paper, we study greedy geometric routing in R2, using the standard Eu- clidean metric. Greedy geometric routing is not always possible in xed-dimensional Euclidean spaces, of course, as is the case, for example, with star graphs. Nevertheless, we show that such greedy geometric routing schemes exist in R2, for 3-connected planar graphs, using the standard Euclidean metric, with coordinates that can be represented succinctly, that is, with O(logn) bits. Moreover, our embedding strategy introduces a coordinate system for R2 that supports distance comparisons using our succinct coordinates. Thus, our scheme can be used to signicantly reduce bandwidth, space, and header size over other recently discovered greedy geometric routing implementations for R2. |
Year | Venue | Keywords |
|---|---|---|
2008 | Clinical Orthopaedics and Related Research | euclidean space,coordinate system,planar graph,star graph,metric space |
Field | DocType | Volume |
Geometric graph theory,Discrete mathematics,Outerplanar graph,Combinatorics,Beta skeleton,Spatial network,Random geometric graph,Lattice graph,Theta graph,Mathematics,Unit disk graph | Journal | abs/0812.3 |
Citations | PageRank | References |
3 | 0.51 | 33 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael T. Goodrich | 1 | 4351 | 331.47 |
| Darren Strash | 2 | 238 | 17.72 |