Succinct Greedy Geometric Routing in R^2
Michael T. Goodrich, Darren Strash · 2008
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 R², using the standard Euclidean metric. Greedy geometric routing is not always possible in fixed-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 R², for 3-connected planar graphs, using the standard Euclidean metric, with coordinates that can be represented succinctly, that is, with O(log n) bits. Moreover, our embedding strategy introduces a coordinate system for R² that supports distance comparisons using our succinct coordinates. Thus, our scheme can be used to significantly reduce bandwidth, space, and header size over other recently discovered greedy