{"id":13238,"date":"2021-12-07T21:11:39","date_gmt":"2021-12-08T02:11:39","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13238"},"modified":"2026-06-02T14:59:23","modified_gmt":"2026-06-02T18:59:23","slug":"tr-08-02-spanners-of-additively-weighted-point-sets","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2008\/tr-08-02-spanners-of-additively-weighted-point-sets\/","title":{"rendered":"TR-08-02: Spanners of Additively Weighted Point Sets"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-08-02: Spanners of Additively Weighted Point Sets\n <\/h1>\n \n \n <\/header>\n\n <\/div>\n\n <\/div>\n\n <\/div>\n<\/section>\n\n

Carleton University
\nTechnical Report<\/a> TR-08-02
\nJanuary 28, 2008<\/p>\n\n\n\n

Spanners of Additively Weighted Point Sets<\/h2>\n\n\n\n
\n
\n
\n
\n
\n
\n
\n
\n

Mathieu Couture, Paz Carmi, Prosenjit Bose<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n

Abstract<\/h3>\n

We study the problem of computing geometric spanners for (additively) weighted point sets. A weighted point set is a set of pairs $(p,r)$ where $p$ is a point in the plane and $r$ is a real number. The distance between two points $(p_i,r_i)$ and $(p_j,r_j)$ is defined as $|p_ip_j|-r_i-r_j$. We show that in the case where all $r_i$ are positive numbers and $|p_ip_j|geq r_i+r_j$ for all $i,j$ (in which case the points can be seen as non-intersecting disks in the plane), a variant of the Yao graph is a $(1+epsilon)$-spanner that has a linear number of edges. We also show that the Additively Weighted Delaunay graph (the face-dual of the Additively Weighted Voronoi diagram) has constant spanning ratio. The straight line embedding of the Additively Weighted Delaunay graph may not be a plane graph. We show how to compute a plane embedding that also has a constant spanning ratio.<\/p>\n

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

Carleton University Technical Report TR-08-02 January 28, 2008 Spanners of Additively Weighted Point Sets Mathieu Couture, Paz Carmi, Prosenjit Bose Abstract We study the problem of computing geometric spanners for (additively) weighted point sets. A weighted point set is a set of pairs $(p,r)$ where $p$ is a point in the plane and $r$ is […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12410,"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-13238","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13238","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=13238"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13238\/revisions"}],"predecessor-version":[{"id":13239,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13238\/revisions\/13239"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12410"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13238"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13238"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}