{"id":13230,"date":"2021-12-07T21:04:48","date_gmt":"2021-12-08T02:04:48","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13230"},"modified":"2026-06-02T14:59:23","modified_gmt":"2026-06-02T18:59:23","slug":"tr-07-22-spanners-of-complete-k-partite-geometric-graphs","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-22-spanners-of-complete-k-partite-geometric-graphs\/","title":{"rendered":"TR-07-22: Spanners of complete k-Partite Geometric Graphs"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-07-22: Spanners of complete k-Partite Geometric Graphs\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-07-22
\nDecember 5, 2007<\/p>\n\n\n\n

Spanners of complete k-Partite Geometric Graphs<\/h2>\n\n\n\n
\n
\n
\n
\n
\n
\n
\n
\n

Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Pat Morin, Michiel Smid<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n

Abstract<\/h3>\n

We address the following problem: Given a complete $k$-partite geometric graph $K$ whose vertex set is a set of $n$ points in $\\mathbb{R}^d$, compute a spanner of $K$ that has a “small” stretch factor and “few” edges. We present two algorithms for this problem. The first algorithm computes a $(5+\\epsilon)$-spanner of $K$ with $O(n)$ edges in $O(n \\log n)$ time. The second algorithm computes a $(3+\\epsilon)$-spanner of $K$ with $O(n \\log n)$ edges in $O(n \\log n)$ time. The latter result is optimal: We show that for any $2 \\leq k \\leq n – \\Theta(\\sqrt{n \\log n} )$, spanners with $O(n \\log n)$ edges and stretch factor less than $3$ do not exist for all complete $k$-partite geometric graphs.<\/p>\n

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

Carleton University Technical Report TR-07-22 December 5, 2007 Spanners of complete k-Partite Geometric Graphs Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Pat Morin, Michiel Smid Abstract We address the following problem: Given a complete $k$-partite geometric graph $K$ whose vertex set is a set of $n$ points in $\\mathbb{R}^d$, compute a spanner of $K$ […]<\/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-13230","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13230","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=13230"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13230\/revisions"}],"predecessor-version":[{"id":13231,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13230\/revisions\/13231"}],"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=13230"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13230"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}