2008/12/19 by Michael T. Goodrich, Goodrich, Michael T., Darren Strash +1
Computer Science · #C.2.1 #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.0812.3893
19 pages, 5 figures. To appear at 20th International Symposium on Algorithms and Computation (ISAAC 2009)
arxiv created 2009/10/02 · arxiv updated 2009/12/01
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 R2, 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 R2 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 R2.