World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

In various wireless networking settings, node locations determine a network’s topology, allowing the network to be modelled by a geometric graph drawn in the plane. Without any additional information, local geometric routing algorithms can guarantee delivery to the target node only in restricted classes of geometric graphs, such as triangulations. In order to guarantee delivery on more general classes of geometric graphs (e.g., convex subdivisions or planar subdivisions), previous local geometric routing algorithms required Θ(logn) state bits to be stored and passed with the message. We present the first local geometric routing algorithm using only one state bit to guarantee delivery on convex subdivisions and, when the algorithm has knowledge of the incoming port (the preceding node on the route), the first stateless local geometric routing algorithm that guarantees delivery on edge-augmented monotone subdivisions (including all convex subdivisions). We also show that Ω(logn) state bits are necessary in planar subdivisions in which faces may have three or more reflex vertices.

Communicated by Joe Mitchell


  • 1. M. de Berg, M. van Kreveld, R. van Oostrum and M. Overmars , Simple traversal of a subdivision without extra storage, Int. J. Geog. Inf. Sci. 11(4) (1997) 359–373. Crossref, ISIGoogle 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. Comp. Geom. & Appl. 12(4) (2002) 283–295. LinkGoogle Scholar
  • 3. P. Bose, P. Carmi and S. Durocher , Bounding the locality of distributed routing algorithms, Dist. Comp. 26(1) (2013) 39–58. Crossref, ISIGoogle Scholar
  • 4. P. Bose, S. Durocher, D. Mondal, M. Peabody, M. Skala and M. A. Wahid , Local routing in convex subdivisions, in Proc. SOFSEM, Vol. 8939 (LNCS, Springer, 2015), pp. 140–151. CrossrefGoogle Scholar
  • 5. P. Bose and P. Morin , An improved algorithm for subdivision traversal without extra storage, Int. J. Comp. Geom. & Appl. 12(4) (2002) 297–308. Link, ISIGoogle Scholar
  • 6. P. Bose and P. Morin , Competitive online routing in geometric graphs, Theor. Comp. Sci. 324 (2004) 273–288. Crossref, ISIGoogle Scholar
  • 7. P. Bose and P. Morin , Online routing in triangulations, SIAM J. Comp. 33(4) (2004) 937–951. Crossref, ISIGoogle Scholar
  • 8. P. Bose, P. Morin, I. Stojmenović and J. Urrutia , Routing with guaranteed delivery in ad hoc wireless networks, Wireless Net. 7(6) (2001) 609–616. Crossref, ISIGoogle Scholar
  • 9. M. Braverman , On ad hoc routing with guaranteed delivery, in Proc. ACM PODC, Vol. 27 (2008), p. 418. CrossrefGoogle Scholar
  • 10. E. Chavez, S. Dobrev, E. Kranakis, J. Opatrny, L. Stacho and J. Urrutia , Traversal of a quasi-planar subdivision without using mark bits, J. Interconn. Net. 5(4) (2004) 395–408. LinkGoogle Scholar
  • 11. D. Chen, L. Devroye, V. Dujmović and P. Morin , Memoryless routing in convex subdivisions: Random walks are optimal, Comp. Geom.: Theory & Appl. 45(4) (2012) 178–185. Crossref, ISIGoogle Scholar
  • 12. 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, ISIGoogle Scholar
  • 13. G. G. Finn, Routing and addressing problems in large metropolitan-scale internetworks, Technical Report ISI/RR-87-180 (Information Sciences Institute, 1987). Google Scholar
  • 14. H. Frey, S. Ruehrup and I. Stojmenovic , Routing in wireless sensor networks, In S. MisraI. WoungagS. Misra, editors, Guide to Wireless Ad Hoc Networks, Chap. 4 (Springer-Verlag, 2009), pp. 81–111. Google Scholar
  • 15. X. Guan, Face Routing in Wireless ad-hoc Networks (PhD thesis, Univ. Toronto, 2009). Google Scholar
  • 16. E. Kranakis, H. Singh and J. Urrutia , Compass routing on geometric networks, in Proc. CCCG, Vol. 11 (1999), pp. 51–54. Google Scholar
  • 17. F. Kuhn, R. Wattenhofer and A. Zollinger , Ad hoc networks beyond unit disk graphs, Wireless Networks 14(5) (2008) 715–729. Crossref, ISIGoogle Scholar
  • 18. P. Morin, Online Routing in Geometric Graphs, (PhD thesis, Carleton Univ., 2001). Google Scholar
  • 19. J. Urrutia , Handbook wireless net. & mob. comp, in I. Stojmenovic, editor, Routing with Guaranteed Delivery in Geometric and Wireless Networks (John Wiley & Sons, Inc., 2002), pp. 393–406. Google Scholar
  • 20. M. A. Wahid, Local geometric routing algorithms for edge-augmented planar graphs, (Master’s thesis, Univ. Manitoba, 2013). Google Scholar
Remember to check out the Most Cited Articles!

Check out these titles in image analysis!