Thumbnail
Access Restriction
Subscribed

Author Lanthier, Mark A. ♦ Nussbaum, Doron ♦ Wang, Tsuo-Jung
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2009
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword 1-Center ♦ Algorithms ♦ Approximation ♦ Meeting point ♦ Robots ♦ Shortest path ♦ Terrain ♦ Weighted
Abstract In this article, we discuss the problem of determining a meeting point of a set of scattered robots $\textit{R}$ &equls; ${r_{1},$ $r_{2},…,r_{s}}$ in a weighted terrain P, which has $\textit{n}$ > $\textit{s}$ triangular faces. Our algorithmic approach is to produce a discretization of P by producing a graph $\textit{G}$ &equls; ${V^{G},$ $E^{G}},$ which lies on the surface of P. For a chosen vertex $\textit{&pprime;}$ ∈ $V^{G},$ we define $‖Π(r_{i},$ $\textit{&pprime;})‖$ as the minimum weight cost of traveling from $r_{i}$ to $\textit{&pprime;}.$ We show that $min\textit{&pprime;}$ ∈ $V^{G}}{max_{1≤i≤s}$ ${‖Π(r_{i},&pprime;)‖}}$ ≤ $min_{p*∈P}{max_{1≤i≤s}{‖Π(r_{i},p*)‖}}$ + $2\textit{W}|\textit{L}|,$ where $\textit{L}$ is the longest edge of P, $\textit{W}$ is the maximum cost weight of a face of P, and $\textit{p}*$ is the optimal solution. Our algorithm requires $\textit{O}(\textit{snm}$ $log(\textit{snm})$ + $snm^{2})$ time to run, where $\textit{m}$ = $\textit{n}$ in the Euclidean metric and $\textit{m}$ = $n^{2}$ in the weighted metric. However, we show, through experimentation, that only a constant value of $\textit{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 $\textit{O}(\textit{sn}$ $log(\textit{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 $\textit{&pprime;},$ with minimal or no additional accuracy error when comparing $\textit{&pprime;}$ to $\textit{p}*.$
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2009-02-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 13
Page Count 27
Starting Page 1.3
Ending Page 1.29


Open content in new tab

   Open content in new tab
Source: ACM Digital Library