{"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":"2026-06-02T14:59:24","modified_gmt":"2026-06-02T18:59:24","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":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-07-08: On a Family of Strong Geometric Spanners that Admit Local Routing Strategies\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/\">Technical Report<\/a> TR-07-08<br>\nMarch 1, 2007<\/p>\n\n\n\n<h2 id=\"on-a-family-of-strong-geometric-spanners-that-admit-local-routing-strategies\" class=\"wp-block-heading\">On a Family of Strong Geometric Spanners that Admit Local Routing Strategies<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<p class=\"tr_t3\">Prosenjit Bose, Paz Carmi, Mathieu Couture, Michiel Smid, Daming Xu<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div>\n<h3>Abstract<\/h3>\n<p>We introduce a family of directed geometric graphs, denoted G(lambda,theta), that depend on two parameters lambda and theta. For 0 &lt;= theta &lt; pi\/2 and 1\/2 &lt; lambda &lt; 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<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-07-08.pdf\">TR-07-08.pdf<\/a><\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>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 &lt;= theta &lt; pi\/2 [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12385,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-13201","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13201","targetHints":{"allow":["GET"]}}],"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\/2"}],"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"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13201"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}