Paper by Erik D. Demaine
- Prosenjit Bose, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, Alejandro López-Ortiz, Pat Morin, and J. Ian Munro, “Online Routing in Convex Subdivisions”, International Journal of Computational Geometry and Applications, volume 12, number 4, August 2002, pages 283–295. Special issue of selected papers from the 11th Annual International Symposium on Algorithms and Computation, 2000.
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.
- The paper is 14 pages.
- The paper is available in PostScript (648k) and gzipped PostScript (88k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- ISAAC2000 (Online Routing in Convex Subdivisions)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 19, 2021 by