Memoryless routing in convex subdivisions: Random walks are optimal

A memoryless routing algorithm is one in which the decision about the next edge on the route to a vertex t for a packet currently located at vertex v is made based only on the coordinates of v, t  , and the neighborhood, N(v)N(v), of v  . The current paper explores the limitations of such algorithms by showing that, for any (randomized) memoryless routing algorithm AA, there exists a convex subdivision on which AA takes Ω(n2)Ω(n2) expected time to route a message between some pair of vertices. Since this lower bound is matched by a random walk, this result implies that the geometric information available in convex subdivisions does not reduce the worst-case routing time for this class of routing algorithms. The current paper also shows the existence of triangulations for which the Random-Compass algorithm proposed by Bose et al. (2002, 2004) requires 2Ω(n)2Ω(n) time to route between some pair of vertices.