In this article, 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 {V G, EG}, which lies on the surface of P. For a chosen vertex ε VG, we define ∏(ri, ) as the minimum weight cost of traveling from ri to . We show that min p ε V G{max1≤i≤s {∏(r i,)}} ≤ minp*εP{max 1≤i≤s{∏(ri,p*)}} + 2WL, 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 , with minimal or no additional accuracy error when comparing to p*.

, , , , , , ,
Journal of Experimental Algorithmics
Carleton University

Lanthier, M, Nussbaum, D, & Wang, T.-J. (Tsuo-Jung). (2008). Computing an approximation of the 1-center problem on weighted terrain surfaces. In Journal of Experimental Algorithmics (Vol. 13). doi:10.1145/1412228.1412231