Paper by Erik D. Demaine

Reference:

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”, in Proceedings of the 11th Annual International Symposium on Algorithms and Computation (ISAAC 2000), Lecture Notes in Computer Science, volume 1969, Taipei, Taiwan, December 18–20, 2000, pages 47–59.

BibTeX

@InProceedings{ISAAC2000,
  AUTHOR        = {Prosenjit Bose and Andrej Brodnik and Svante Carlsson and
                   Erik D. Demaine and Rudolf Fleischer and Alejandro
                   L\'opez-Ortiz and Pat Morin and J. Ian Munro},
  TITLE         = {Online Routing in Convex Subdivisions},
  BOOKTITLE     = {Proceedings of the 11th Annual International Symposium on
                   Algorithms and Computation (ISAAC 2000)},
  YEAR          = 2000,
  SERIES        = {Lecture Notes in Computer Science},
  SERIESURL     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 1969,
  ADDRESS       = {Taipei, Taiwan},
  MONTH         = {December 18--20},
  PAGES         = {47--59},

  award         = {Invited to special issue of \emph{International Journal of Computational Geometry and Applications}.},
  copyright     = {The paper is \copyright Springer-Verlag.},
  length        = {12 pages},
  papers        = {ObliviousRouting_IJCGA2002},
  doi           = {https://dx.doi.org/10.1007/3-540-40996-3_5},
  dblp          = {https://dblp.org/rec/conf/isaac/BoseMBCDFML00},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1007/3-540-40996-3_5">SpringerLink</A>.},
}

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.

Comments:

This paper is also available from SpringerLink.

Copyright:

The paper is \copyright Springer-Verlag.

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (636k) and gzipped PostScript (85k).

See information on file formats.

[Google Scholar search]

Related papers:

ObliviousRouting_IJCGA2002 (Online Routing in Convex Subdivisions)