In this paper we discuss the problem of determining a meeting point of a set of scattered robots R = {r 1, r 2,..., r s} 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 = {V G,E G} which lies on the surface of P. For a chosen vertex p′ ∈ V G, we define II(r i, p′) as the minimum weight cost of traveling from ri to p′. We show that minp′∈V G{max1≤i≤s{II(ri, p′)}} ≤ minp*∈P{max 1≤i≤s{II(r i, p*)}} +W|L| 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. This error of W|L| is an upper bound which can be stated more precisely as W|L|(1+2k)/2(m+1), where m is an adjustable non-zero parameter and k is the maximum number of segments of II(ri, p′) ( 1 ≤ i ≤ s. Our algo-rithm requires O(snmlog(snm)+snm 2) 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 accu-rate 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 se-lection) of the robots we can improve the running time for finding p′, with minimal or no additional accuracy error when comparing p′ to p*.

Additional Metadata
Keywords 1-center, Algorithms, Approximation, Meeting point, Robots, Shortest path, Terrain, Weighted
Conference Theory of Computing 2005 - 11th Computing: The Australasian Theory Symposium, CATS 2005
Citation
Lanthier, M, Nussbaum, D, & Wang, T.-J. (Tsuo-Jung). (2005). Calculating the meeting point of scattered robots on weighted terrain surfaces. Presented at the Theory of Computing 2005 - 11th Computing: The Australasian Theory Symposium, CATS 2005.