Succinct Greedy Geometric Routing in the Euclidean Plane

Details Succinct Greedy Geometric Routing in the Euclidean Plane Succinct Greedy Geometric Routing in the Euclidean Plane

2008-12-19

arxiv.org/abs/0812.3893v3

Computer Science

Computational Geometry

19 pages, 5 figures. To appear at 20th International Symposium on Algorithms and Computation (ISAAC 2009)

Scientific paper

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. We show that greedy geometric routing schemes exist for the Euclidean metric in R^2, for 3-connected planar graphs, with coordinates that can be represented succinctly, that is, with O(log n) bits, where n is the number of vertices in the graph. Moreover, our embedding strategy introduces a coordinate system for R^2 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 geometric routing implementations for R^2.

Affiliated with

Also associated with

No associations

Rating

Succinct Greedy Geometric Routing in the Euclidean Plane does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Succinct Greedy Geometric Routing in the Euclidean Plane, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Succinct Greedy Geometric Routing in the Euclidean Plane will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-103518