{"id":13114,"date":"2021-12-06T18:38:56","date_gmt":"2021-12-06T23:38:56","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13114"},"modified":"2026-06-02T14:59:24","modified_gmt":"2026-06-02T18:59:24","slug":"tr-04-05-calculating-the-meeting-point-of-scattered-robots-on-weighted-terrain-surfaces","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/tr-04-05-calculating-the-meeting-point-of-scattered-robots-on-weighted-terrain-surfaces\/","title":{"rendered":"TR-04-05: Calculating the Meeting Point of Scattered Robots on Weighted Terrain Surfaces"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-04-05: Calculating the Meeting Point of Scattered Robots on Weighted Terrain Surfaces\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-04-05
\nAugust 2004<\/p>\n\n\n\n

Calculating the Meeting Point of Scattered Robots on Weighted Terrain Surfaces<\/h2>\n\n\n\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
Mark Lanthier, Doron Nussbaum, Tsuo-Jung Wang<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n

In this paper we discuss the problem of determining a meeting point of a set of scattered robots R = {r1, r2, …, rs} in a weighted terrain P which has n > s triangular faces. Our algorithmic approach is to produce a discretization of P by producing a graph G = {VG, EG} which lies on the surface of P. For a chosen vertex p’ in VG, we define || \ufffd(ri, p’) || as the minimum weight cost of traveling from ri to p’. We show thatmin{p’ in VG}{max{1<= i <= s} {|| \ufffd(ri, p’) ||}} <= min{p* in P}{max{1 <= i <= s}{|| \ufffd(ri, p*) ||}} + W|L|<\/p>\n

where L is the longest edge of P, W is the maximum cost weight of a face of P, and p* is the optimal solution. Our algorithm requires O(snm log(snm) + snm2) time to run, where m = n in the Euclidean metric and m = n2 in the weighted metric. However, we show through experimentation that only a constant value of m is required (e.g., m = 8) in order to produce very accurate solutions (< 1% error). Hence, for typical terrain data, the expected running time of our algorithm is O(sn log(sn)). Also, as part of our experiments we show that by using geometrical subsets (i.e., 2D\/3D convex hulls, 2D\/3D bounding boxes and random selection) of the robots we can improve the running time for finding p’, with minimal or no additional accuracy error when comparing p’ to p*.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n

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

Carleton University Technical Report TR-04-05 August 2004 Calculating the Meeting Point of Scattered Robots on Weighted Terrain Surfaces Mark Lanthier, Doron Nussbaum, Tsuo-Jung Wang Abstract In this paper we discuss the problem of determining a meeting point of a set of scattered robots R = {r1, r2, …, rs} in a weighted terrain P which […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12325,"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-13114","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13114","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=13114"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13114\/revisions"}],"predecessor-version":[{"id":13115,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13114\/revisions\/13115"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12325"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13114"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13114"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}