Competitive Online Routing on Delaunay Triangulations
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.
|Keywords||competitive algorithm, Delaunay triangulation, Online routing|
|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