Competitive online routing on Delaunay triangulations
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.
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