### Computing an approximation of the 1-center problem on weighted terrain surfacesComputing an approximation of the 1-center problem on weighted terrain surfaces 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

Source: ACM Digital Library