Description:
<jats:p>
In this article, we discuss the problem of determining a meeting point of a set of scattered robots
<jats:italic>R</jats:italic>
= {
<jats:italic>r</jats:italic>
<jats:sub>1</jats:sub>
,
<jats:italic>r</jats:italic>
<jats:sub>2</jats:sub>
,…,
<jats:italic>
r
<jats:sub>s</jats:sub>
</jats:italic>
} in a weighted terrain P, which has
<jats:italic>n</jats:italic>
>
<jats:italic>s</jats:italic>
triangular faces. Our algorithmic approach is to produce a discretization of P by producing a graph
<jats:italic>G</jats:italic>
= {
<jats:italic>
V
<jats:sup>G</jats:sup>
</jats:italic>
,
<jats:italic>
E
<jats:sup>G</jats:sup>
</jats:italic>
}, which lies on the surface of P. For a chosen vertex
<jats:italic>p′</jats:italic>
∈
<jats:italic>
V
<jats:sup>G</jats:sup>
</jats:italic>
, we define ‖Π(
<jats:italic>
r
<jats:sub>i</jats:sub>
</jats:italic>
,
<jats:italic>p′</jats:italic>
)‖ as the minimum weight cost of traveling from
<jats:italic>
r
<jats:sub>i</jats:sub>
</jats:italic>
to
<jats:italic>p′</jats:italic>
. We show that min
<jats:sub>
<jats:italic>p′</jats:italic>
∈
<jats:italic>
V
<jats:sup>G</jats:sup>
</jats:italic>
</jats:sub>
{max
<jats:sub>
1≤
<jats:italic>i</jats:italic>
≤
<jats:italic>s</jats:italic>
</jats:sub>
{‖Π(
<jats:italic>
r
<jats:sub>i</jats:sub>
</jats:italic>
,
<jats:italic>p′</jats:italic>
)‖}} ≤ min
<jats:sub>
<jats:italic>p</jats:italic>
*∈P
</jats:sub>
{max
<jats:sub>
1≤
<jats:italic>i</jats:italic>
≤
<jats:italic>s</jats:italic>
</jats:sub>
{‖Π(
<jats:italic>
r
<jats:sub>i</jats:sub>
</jats:italic>
,
<jats:italic>p</jats:italic>
*)‖}} + 2
<jats:italic>W</jats:italic>
|
<jats:italic>L</jats:italic>
|, where
<jats:italic>L</jats:italic>
is the longest edge of P,
<jats:italic>W</jats:italic>
is the maximum cost weight of a face of P, and
<jats:italic>p</jats:italic>
* is the optimal solution. Our algorithm requires
<jats:italic>O</jats:italic>
(
<jats:italic>snm</jats:italic>
log(
<jats:italic>snm</jats:italic>
) +
<jats:italic>snm</jats:italic>
<jats:sup>2</jats:sup>
) time to run, where
<jats:italic>m</jats:italic>
=
<jats:italic>n</jats:italic>
in the Euclidean metric and
<jats:italic>m</jats:italic>
=
<jats:italic>n</jats:italic>
<jats:sup>2</jats:sup>
in the weighted metric. However, we show, through experimentation, that only a constant value of
<jats:italic>m</jats:italic>
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
<jats:italic>O</jats:italic>
(
<jats:italic>sn</jats:italic>
log(
<jats:italic>sn</jats:italic>
)). 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
<jats:italic>p′</jats:italic>
, with minimal or no additional accuracy error when comparing
<jats:italic>p′</jats:italic>
to
<jats:italic>p</jats:italic>
*.
</jats:p>