{"id":{"repo_id":"ottawa-retro","oai_identifier":"oai:ruor.uottawa.ca:10393/8932"},"canonical_url":"https://search.dev.ndltd.org/etd/ottawa-retro/oai:ruor.uottawa.ca:10393/8932","repository":{"repo_id":"ottawa-retro","name":"University of Ottawa","base_url":"https://ruor.uottawa.ca/server/oai/request"},"display":{"title":"Compass routing on geometric graphs.","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Singh, Harvinder."],"institution":"University of Ottawa (Canada)","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Urrutia, J.,"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009-03-23T17:40:22Z","date_published":"2009-03-23T17:40:22Z","updated_at":"2026-07-24T03:39:27Z","subjects":["Computer Science."],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["Source: Masters Abstracts International, Volume: 38-03, page: 0731.","9780612452503","http://dx.doi.org/10.20381/ruor-7564"],"render_values":[{"text":"Source: Masters Abstracts International, Volume: 38-03, page: 0731.","href":null,"code":true},{"text":"9780612452503","href":null,"code":true},{"text":"http://dx.doi.org/10.20381/ruor-7564","href":"http://dx.doi.org/10.20381/ruor-7564","code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/10393/8932","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Urrutia, J.,"]},{"key":"dc:creator","label":"Author","values":["Singh, Harvinder."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2009-03-23T17:40:22Z","1999"]},{"key":"dc:publisher","label":"Institution","values":["University of Ottawa (Canada)"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["Source: Masters Abstracts International, Volume: 38-03, page: 0731.","9780612452503","http://hdl.handle.net/10393/8932","http://dx.doi.org/10.20381/ruor-7564"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:format","label":"Dc Format","values":["77 p.","application/pdf"]},{"key":"dc:title","label":"Title","values":["Compass routing on geometric graphs."]}]}],"canonical_facts":{"dc:contributor":["Urrutia, J.,"],"dc:creator":["Singh, Harvinder."],"dc:date":["2009-03-23T17:40:22Z","1999"],"dc:description":["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."],"dc:format":["77 p.","application/pdf"],"dc:identifier":["Source: Masters Abstracts International, Volume: 38-03, page: 0731.","9780612452503","http://hdl.handle.net/10393/8932","http://dx.doi.org/10.20381/ruor-7564"],"dc:publisher":["University of Ottawa (Canada)"],"dc:subject":["Computer Science."],"dc:title":["Compass routing on geometric graphs."],"dc:type":["Thesis"]},"updated_at":"2026-07-24T03:39:27Z"}