Let $G$ be a graph, $s \in G$ be a source node and $t \in 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.

This work was supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC) and the Fonds Québécois de la Recherche — Science et Technologies (FQRNT). An extended abstract of this paper appeared in SWAT 2014.

Communicated by S. Fekete

Keywords:

References

1. F. Aurenhammer, R. Klein and D.-T. Lee, Voronoi Diagrams and Delaunay Triangulations (World Scientific, 2013). Link, Google Scholar
2. P. Bose, A. Brodnik, S. Carlsson, E. D. Demaine, R. Fleischer, A. López-Ortiz, P. Morin and I. Munro, Online routing in convex subdivisions, Int. J. Comput. Geom. Appl. 12(4) (2002) 283–295. Link, Web of Science, Google Scholar
3. P. Bose, P. Carmi and S. Durocher, Bounding the locality of distributed routing algorithms, Dist. Comp. 26(1) (2013) 39–58. Crossref, Web of Science, Google Scholar
4. P. Bose, J.-L. De Carufel, S. Durocher and P. Taslakian, Competitive online routing on Delaunay triangulations, Algorithm Theory — SWAT 2014 — 14th Scandinavian Symp. Workshops, Copenhagen, Denmark, July 2–4 (2014), pp. 98–109. Google Scholar
5. P. Bose and J. M. Keil, On the stretch factor of the constrained Delaunay triangulation, ISVD (2006), pp. 25–31. Google Scholar
6. P. Bose and P. Morin, Competitive online routing in geometric graphs, Theor. Comp. Sci. 324(2–3) (2004) 273–288. Crossref, Web of Science, Google Scholar
7. P. Bose and P. Morin, Online routing in triangulations, SIAM J. Comp. 33(4) (2004) 937–951. Crossref, Web of Science, Google Scholar
8. P. Bose, P. Morin, I. Stojmenović and J. Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Wireless N 7(6) (2001) 609–616. Crossref, Web of Science, Google Scholar
9. M. Braverman, On ad hoc routing with guaranteed delivery, PODC, Vol. 27 (ACM, 2008), p. 418. Google Scholar
10. D. Chen, L. Devroye, V. Dujmović and P. Morin, Memoryless routing in convex subdivisions: Random walks are optimal, EuroCG (2010), pp. 109–112. Google Scholar
11. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd edn. (MIT Press, 2009). Google Scholar
12. S. Cui, I. A. Kanj and G. Xia, On the stretch factor of Delaunay triangulations of points in convex position, Comp. Geom. 44(2) (2011) 104–109. Crossref, Web of Science, Google Scholar
13. E. W. Dijkstra, A note on two problems in connexion with graphs, Numer. Math. 1 (1959) 269–271. Crossref, Google Scholar
14. D. P. Dobkin, S. J. Friedman and K. J. Supowit, Delaunay graphs are almost as good as complete graphs, Disc. Comp. Geom. 5 (1990) 399–407. Crossref, Web of Science, Google Scholar
15. S. Durocher, D. Kirkpatrick and L. Narayanan, On routing with guaranteed delivery in three-dimensional ad hoc wireless networks, Wireless Net. 16 (2010) 227–235. Crossref, Web of Science, Google Scholar
16. M. Fraser, Local routing on tori, Adhoc and Sensor Wireless Net. 6 (2008) 179–196. Web of Science, Google Scholar
17. M. Fraser, E. Kranakis and J. Urrutia, Memory requirements for local geometric routing and traversal in digraphs, CCCG, Vol. 20 (2008), pp. 195–198. Google Scholar
18. X. Guan, Face routing in wireless ad-hoc networks, PhD thesis, University of Toronto (2009). Google Scholar
19. J. M. Keil and C. A. Gutwin, Classes of graphs which approximate the complete euclidean graph, Disc. Comp. Geom. 7 (1992) 13–28. Crossref, Web of Science, Google Scholar
20. E. Kranakis, H. Singh and J. Urrutia, Compass routing on geometric networks, CCCG, Vol. 11 (1999), pp. 51–54. Google Scholar
21. F. Kuhn, R. Wattenhofer and A. Zollinger, Asymptotically optimal geometric mobile adhoc routing, DIALM (ACM, 2002), pp. 24–33. Google Scholar
22. F. Kuhn, R. Wattenhofer and A. Zollinger, Ad-hoc networks beyond unit disk graphs, DIALM-POMC (ACM, 2003), pp. 69–78. Google Scholar
23. A. Okabe, B. Boots, K. Sugihara and S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, Wiley Series in Probability and Statistics (Wiley, 2009). Google Scholar
24. W. Si and A. Y. Zomaya, New memoryless online routing algorithms for Delaunay triangulations, IEEE Trans. Par. Dist. Sys. 23(8) (2012). Web of Science, Google Scholar
25. G. Xia, The stretch factor of the Delaunay triangulation is less than 1.998, SIAM J. Comp. 42(4) (2013) 1620–1659. Crossref, Web of Science, Google Scholar