We consider online routing algorithms for routing between the vertices of embedded planar straight line graphs. Our results include (1) two deterministic memoryless routing algorithms, one that works for all Delaunay triangulations and the other that works for all regular triangulations; (2) a randomized memoryless algorithm that works for all triangulations; (3) an O(1) memory algorithm that works for all convex subdivisions; (4) an O(1) memory algorithm that approximates the shortest path in Delaunay triangulations; and (5) theoretical and experimental results on the competitiveness of these algorithms.

Additional Metadata
Keywords Delaunay triangulations, Online algorithms, Routing, Shortest path, Spanning path
Persistent URL dx.doi.org/10.1137/S0097539700369387
Journal SIAM Journal on Computing
Bose, P, & Morin, P. (2004). Online routing in triangulations. SIAM Journal on Computing, 33(4), 937–951. doi:10.1137/S0097539700369387