20051201
Calculating the meeting point of scattered robots on weighted terrain surfaces
Publication
Publication
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*)}} +WL 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 WL is an upper bound which can be stated more precisely as WL(1+2k)/2(m+1), where m is an adjustable nonzero parameter and k is the maximum number of segments of II(ri, p′) ( 1 ≤ i ≤ s. Our algorithm 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 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*.
Additional Metadata  

Keywords  1center, 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. (TsuoJung). (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.
