20150101
Upper and lower bounds for online routing on delaunay triangulations
Publication
Publication
Consider a weighted graph G whose vertices are points in the plane and edges are line segments between pairs of points whose weight is the Euclidean distance between its endpoints. A routing algorithm on G sends a message from any vertex s to any vertex t in G. The algorithm has a competitive ratio of c if the length of the path taken by the message is at most c times the length of the shortest path from s to t in G. It has a routing ratio of c if the length of the path is at most c times the Euclidean distance from s to t. The algorithm is online if it makes forwarding decisions based on (1) the kneighborhood in G of the message’s current position (for constant k > 0) and (2) limited information stored in the message header. We present an online routing algorithm on the Delaunay triangulation with routing ratio less than 5.90, improving the best known routing ratio of 15.48. Our algorithm makes forwarding decisions based on the 1neighborhood of the current position of the message and the positions of the message source and destination only. We present a lower bound of 5.7282 on the routing ratio of our algorithm, so the 5.90 upper bound is close to the best possible. We also show that the routing (resp., competitive) ratio of any deterministic klocal algorithm is at least 1.70 (resp., 1.23) for the Delaunay triangulation and 2.70 (resp. 1.23) for the L1Delaunay triangulation. In the case of the L1Delaunay triangulation, this implies that even though there always exists a path between s and t whose length is at most 2.61[st], it is not always possible to route a message along a path of length less than 2.70[st] using only local information.
Additional Metadata  

Keywords  Competitive ratio, Delaunay triangulation, Online routing, Routing ratio 
Persistent URL  dx.doi.org/10.1007/9783662483503_18 
Citation 
Bonichon, N. (Nicolas), Bose, P, De Carufel, J.L. (JeanLou), Perković, L. (Ljubomir), & van Renssen, A. (André). (2015). Upper and lower bounds for online routing on delaunay triangulations. doi:10.1007/9783662483503_18
