Name
Abstract | ||
|---|---|---|
In this article, we discuss the problem of determining a meeting point of a set of scattered robots R &equls; {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 &equls; {VG, EG}, which lies on the surface of P. For a chosen vertex &pprime; ∈ VG, we define ‖Π(ri, &pprime;)‖ as the minimum weight cost of traveling from ri to &pprime;. We show that min&pprime; ∈ VG{max1≤i≤s {‖Π(ri,&pprime;)‖}} ≤ minp*∈P{max1≤i≤s{‖Π(ri,p*)‖}} + 2W|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. 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 &pprime;, with minimal or no additional accuracy error when comparing &pprime; to p*. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1412228.1412231 | Journal of Experimental Algorithmics (JEA) |
Keywords | Field | DocType |
terrain,robots,minimum weight cost,1-center problem,shortest path,snm log,meeting point,chosen vertex,1-center,scattered robots r,weighted terrain surface,sn log,algorithmic approach,weighted,additional accuracy error,accurate solution,approximation,weighted terrain,maximum cost weight,algorithms,convex hull | Discretization,Discrete mathematics,Graph,Combinatorics,Mathematical optimization,Shortest path problem,Vertex (geometry),Euclidean distance,Terrain,E8,Minimum weight,Mathematics | Journal |
Volume | Citations | PageRank |
13, | 0 | 0.34 |
References | Authors | |
18 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark A. Lanthier | 1 | 0 | 0.34 |
| Doron Nussbaum | 2 | 89 | 13.49 |
| Tsuo-Jung Wang | 3 | 9 | 1.10 |