论文标题
无线模型中2个代理的三角撤离
Triangle Evacuation of 2 Agents in the Wireless Model
论文作者
论文摘要
\ emph {三角撤离}问题的输入是三角形$ abc $。鉴于三角形周长的起点$ s $，该问题的可行解决方案由两个单位速度轨迹组成，这些轨迹最终访问了$ abc $的周长的每个点。可行解决方案的成本（疏散成本）被定义为所有点$ t $的上限，这是代理商首次访问$ t $的时间，当时是$ t $的距离。 在涵盖单元圆圈的文献中，对类似的疏散类型问题进行了很好的研究，$ \ ell_p $ unit circle $ p \ geq 1 $，the Square和等边三角形。我们将此研究线扩展到任意的非观察三角形。由于我们的搜索域缺乏对称性，我们引入了4种不同的算法问题，这是通过让起始边缘和/或该边缘上的起点$ s $由算法或对手选择的。为此，我们为算法提供了严格的分析，该算法已被证明对先前研究的搜索域是最佳的，并且为每个问题提供了下限。我们的上限和下边界都匹配并自然扩展了仅针对等边三角形建立的先前已知结果。
The input to the \emph{Triangle Evacuation} problem is a triangle $ABC$. Given a starting point $S$ on the perimeter of the triangle, a feasible solution to the problem consists of two unit-speed trajectories of mobile agents that eventually visit every point on the perimeter of $ABC$. The cost of a feasible solution (evacuation cost) is defined as the supremum over all points $T$ of the time it takes that $T$ is visited for the first time by an agent plus the distance of $T$ to the other agent at that time. Similar evacuation type problems are well studied in the literature covering the unit circle, the $\ell_p$ unit circle for $p\geq 1$, the square, and the equilateral triangle. We extend this line of research to arbitrary non-obtuse triangles. Motivated by the lack of symmetry of our search domain, we introduce 4 different algorithmic problems arising by letting the starting edge and/or the starting point $S$ on that edge to be chosen either by the algorithm or the adversary. To that end, we provide a tight analysis for the algorithm that has been proved to be optimal for the previously studied search domains, as well as we provide lower bounds for each of the problems. Both our upper and lower bounds match and extend naturally the previously known results that were established only for equilateral triangles.
