Title: Shortest Paths of Mutually Visible Robots Show Chinese title

Title: 可见机器人的最短路径

Abstract: Given a set of $n$ point robots inside a simple polygon $P$, the task is to move the robots from their starting positions to their target positions along their shortest paths, while the mutual visibility of these robots is preserved. Previous work only considered two robots. In this paper, we present an $O(mn)$ time algorithm, where $m$ is the complexity of the polygon, when all the starting positions lie on a line segment $S$, all the target positions lie on a line segment $T$, and $S$ and $T$ do not intersect. We also argue that there is no polynomial-time algorithm, whose running time depends only on $n$ and $m$, that uses a single strategy for the case where $S$ and $T$ intersect. Show Chinese abstract

Abstract: 给定一个位于简单多边形$P$内的$n$个点机器人，任务是让机器人沿着最短路径从起始位置移动到目标位置，同时保持这些机器人的相互可见性。 以前的研究只考虑了两个机器人。 在本文中，我们提出一个 $O(mn)$ 时间算法，其中 $m$ 是多边形的复杂度，当所有起始位置位于线段 $S$ 上，所有目标位置位于线段 $T$ 上，且 $S$ 和 $T$ 不相交。 我们还认为，不存在一种运行时间仅依赖于$n$和$m$的多项式时间算法，在$S$和$T$相交的情况下，该算法使用单一策略。