The sequence of adjacent nodes (graph walk) visited by a routing algorithm on a graph G between given source and target nodes s and t is a c-competitive route if its length in G is at most c times the length of the shortest path from s to t in G. We present 21.766-, 17.982- and 15.479-competitive online routing algorithms on the Delaunay triangulation of an arbitrary given set of points in the plane. This improves the competitive ratio on Delaunay triangulations from the previous best of 45.749. We present a 7.621-competitive online routing algorithm for Delaunay triangulations of point sets in convex position.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-319-08404-6_9
Citation
Bose, P, De Carufel, J.-L. (Jean-Lou), Durocher, S. (Stephane), & Taslakian, P. (Perouz). (2014). Competitive online routing on Delaunay triangulations. doi:10.1007/978-3-319-08404-6_9