2026-09-22T10:39:04Zhttps://ruor.uottawa.ca/server/oai/request

oai:ruor.uottawa.ca:10393/89322024-02-23T09:03:14Zcom_10393_242col_10393_244

Compass routing on geometric graphs. Singh, Harvinder. Urrutia, J., Computer Science. In this thesis, we introduce a novel routing algorithm which we call "compass routing" to find paths between pairs of points in planar geometric graphs. Our main goal was that of developing, whenever possible, routing algorithms that, using only "local information", the position of our destination and a finite amount of extra memory, find a path from a starting position to our destination. We developed "compass routing" based routing algorithms for trees, Delaunay triangulations and orthogonal convexly embedded geometric graphs. Several related results on various types of geometric graphs were also studied. 2009-03-23T17:40:22Z 2009-03-23T17:40:22Z 1999 1999 Thesis Source: Masters Abstracts International, Volume: 38-03, page: 0731. 9780612452503 http://hdl.handle.net/10393/8932 http://dx.doi.org/10.20381/ruor-7564 77 p. application/pdf University of Ottawa (Canada)