{"id":13201,"date":"2021-12-07T20:42:38","date_gmt":"2021-12-08T01:42:38","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13201"},"modified":"2021-12-07T20:42:38","modified_gmt":"2021-12-08T01:42:38","slug":"tr-07-08-on-a-family-of-strong-geometric-spanners-that-admit-local-routing-strategies","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-08-on-a-family-of-strong-geometric-spanners-that-admit-local-routing-strategies\/","title":{"rendered":"TR-07-08: On a Family of Strong Geometric Spanners that Admit Local Routing Strategies"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-07-08
\nMarch 1, 2007<\/p>\n

On a Family of Strong Geometric Spanners that Admit Local Routing Strategies<\/h2>\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

Prosenjit Bose, Paz Carmi, Mathieu Couture, Michiel Smid, Daming Xu<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n

Abstract<\/h3>\n

We introduce a family of directed geometric graphs, denoted G(lambda,theta), that depend on two parameters lambda and theta. For 0 <= theta < pi\/2 and 1\/2 < lambda < 1, the G(lambda,theta) graph is a strong t-spanner, with t=1\/((1-lambda)cos(theta)). The out-degree of a node in the G(lambda,theta) graph is at most floor(2pi\/(min(theta, arccos(1\/2lambda))). Moreover, we show that routing can be achieved locally on G(lambda,theta). Next, we show that all strong t-spanners are also t-spanners of the unit disk graph. Simulations for various values of the parameters lambda and theta indicate that for random point sets, the spanning ratio of G(lambda,theta) is better than the proven theoretical bounds.<\/p>\n

TR-07-08.pdf<\/a><\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-07-08 March 1, 2007 On a Family of Strong Geometric Spanners that Admit Local Routing Strategies Prosenjit Bose, Paz Carmi, Mathieu Couture, Michiel Smid, Daming Xu Abstract We introduce a family of directed geometric graphs, denoted G(lambda,theta), that depend on two parameters lambda and theta. For 0 <= theta < pi\/2 […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":12385,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"\nTR-07-08: On a Family of Strong Geometric Spanners that Admit Local Routing Strategies - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-07-08 March 1, 2007 On a Family of Strong Geometric Spanners that Admit Local Routing Strategies Prosenjit Bose,\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-08-on-a-family-of-strong-geometric-spanners-that-admit-local-routing-strategies\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-08-on-a-family-of-strong-geometric-spanners-that-admit-local-routing-strategies\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-08-on-a-family-of-strong-geometric-spanners-that-admit-local-routing-strategies\/\",\"name\":\"TR-07-08: On a Family of Strong Geometric Spanners that Admit Local Routing Strategies - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-12-08T01:42:38+00:00\",\"dateModified\":\"2021-12-08T01:42:38+00:00\",\"description\":\"Carleton University Technical Report TR-07-08 March 1, 2007 On a Family of Strong Geometric Spanners that Admit Local Routing Strategies Prosenjit Bose,\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-08-on-a-family-of-strong-geometric-spanners-that-admit-local-routing-strategies\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-08-on-a-family-of-strong-geometric-spanners-that-admit-local-routing-strategies\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-08-on-a-family-of-strong-geometric-spanners-that-admit-local-routing-strategies\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 2007\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-07-08: On a Family of Strong Geometric Spanners that Admit Local Routing Strategies\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-07-08: On a Family of Strong Geometric Spanners that Admit Local Routing Strategies - School of Computer Science","description":"Carleton University Technical Report TR-07-08 March 1, 2007 On a Family of Strong Geometric Spanners that Admit Local Routing Strategies Prosenjit Bose,","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-08-on-a-family-of-strong-geometric-spanners-that-admit-local-routing-strategies\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-08-on-a-family-of-strong-geometric-spanners-that-admit-local-routing-strategies\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-08-on-a-family-of-strong-geometric-spanners-that-admit-local-routing-strategies\/","name":"TR-07-08: On a Family of Strong Geometric Spanners that Admit Local Routing Strategies - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-12-08T01:42:38+00:00","dateModified":"2021-12-08T01:42:38+00:00","description":"Carleton University Technical Report TR-07-08 March 1, 2007 On a Family of Strong Geometric Spanners that Admit Local Routing Strategies Prosenjit Bose,","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-08-on-a-family-of-strong-geometric-spanners-that-admit-local-routing-strategies\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-08-on-a-family-of-strong-geometric-spanners-that-admit-local-routing-strategies\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-08-on-a-family-of-strong-geometric-spanners-that-admit-local-routing-strategies\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 2007","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/"},{"@type":"ListItem","position":5,"name":"TR-07-08: On a Family of Strong Geometric Spanners that Admit Local Routing Strategies"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13201"}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/49"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=13201"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13201\/revisions"}],"predecessor-version":[{"id":13202,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13201\/revisions\/13202"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12385"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13201"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}