Name
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 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′ ε VG, we define ||II(ri, p′)|| as the minimum weight cost of traveling from ri to p′ We show that minp′εVG{max1≤i≤s {||II(ri,P′)|| ≤ min p*εP{max1≤i≤s{||II(ri, 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 [EQUATION], where m is an adjustable non-zero parameter and k is the maximum number of segments of II(ri, p′) ∀ 1 ≤ i ≤ s. 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 (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*. |
Year | Venue | Keywords |
|---|---|---|
2005 | CATS | robots,algorithms,upper bound,approximation,shortest path,convex hull,terrain |
Field | DocType | ISBN |
Discretization,Discrete mathematics,Combinatorics,Shortest path problem,Vertex (geometry),Upper and lower bounds,Euclidean distance,Regular polygon,Minimum weight,Mathematics,Bounding overwatch | Conference | 1-920682-23-6 |
Citations | PageRank | References |
9 | 0.76 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Lanthier | 1 | 168 | 11.84 |
| Doron Nussbaum | 2 | 89 | 13.49 |
| Tsuo-Jung Wang | 3 | 9 | 1.10 |