Let G be a graph, ψ G be a source node and ψ G be a target node. The sequence of adjacent nodes (graph walk) visited by a routing algorithm 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 a 15.479-competitive online routing algorithm 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 also present a 7.621-competitive online routing algorithm for Delaunay triangulations of point sets in convex position.

Additional Metadata
Keywords competitive algorithm, Delaunay triangulation, Online routing
Persistent URL dx.doi.org/10.1142/S0218195917500066
Journal International Journal of Computational Geometry and Applications
Bose, P, De Carufel, J.-L. (Jean-Lou), Durocher, S. (Stephane), & Taslakian, P. (Perouz). (2017). Competitive Online Routing on Delaunay Triangulations. International Journal of Computational Geometry and Applications, 27(4), 241–253. doi:10.1142/S0218195917500066