Online Routing in Convex Subdivisions. P. Bose, A. Brodnik, S. Carlsson, E. D. Demaine, R. Fleischer, A. López-Ortiz, P. Morin, and J. I. Munro. To appear in International Journal of Computational Geometry and Applications, 2002, Also in Proceedings of the 11th Annual International Symposium on Algorithms and Computation (ISAAC 2000), Lecture Notes in Computer Science, Taipei, Taiwan, December 18-20, 2000. PostScript file.
Abstract. We consider online
routing algorithms for finding paths between the vertices of plane graphs. We
show (1) there exists a routing algorithm for arbitrary triangulations that has
no memory and uses no randomization, (2) no equivalent result is possible for convex
subdivisions, (3) there is no competitive online routing algorithm under the
Euclidean distance metric in arbitrary triangulations, and (4) there is no
competitive online routing algorithm under the link distance metric even when
the input graph is restricted to be a Delaunay, greedy, or minimum-weight
triangulation.