论文标题
脂肪机器人的相互可见性问题
The Mutual Visibility Problem for Fat Robots
论文作者
论文摘要
给定欧几里得平面中的一组$ n \ geq 1 $单位磁盘机器人，我们考虑了提供相互可见性的基本问题：机器人必须自行重新定位才能达到彼此见面的配置。在障碍物下出现了这个问题，如果它们之间的直线段上有第三个机器人，则机器人看不到另一个机器人。 Sharma等人解决了这个问题。 [G. Sharma，R。Alsaedi，C。Busch和S. Mukhopadhyay。带有灯的脂肪机器人的完整可见性问题。在第19届分布式计算和网络国际会议论文集，第1-4页，2018年。]在发光机器人模型中，每个机器人都配备了外部可见光，可以使用9种颜色，使用9种颜色和$ O（n）$ rounds来假设固定颜色的颜色。在这项工作中，我们提出了一种仅需要2种颜色和$ o（n）$回合的算法。颜色的数量是最佳的，因为点机器人至少需要两种颜色[G.A. Di Luna，P。Flocchini，S.G。Chaudhuri，F。Poloni，N。Santoro和G. Viglietta。发光机器人相互可见性，没有碰撞。信息与计算，254：392-418，2017]。
Given a set of $n \geq 1$ unit disk robots in the Euclidean plane, we consider the fundamental problem of providing mutual visibility to them: the robots must reposition themselves to reach a configuration where they all see each other. This problem arises under obstructed visibility, where a robot cannot see another robot if there is a third robot on the straight line segment between them. This problem was solved by Sharma et al. [G. Sharma, R. Alsaedi, C. Busch, and S. Mukhopadhyay. The complete visibility problem for fat robots with lights. In Proceedings of the 19th International Conference on Distributed Computing and Networking, pages 1-4, 2018.] in the luminous robots model, where each robot is equipped with an externally visible light that can assume colors from a fixed set of colors, using 9 colors and $O(n)$ rounds. In this work, we present an algorithm that requires only 2 colors and $O(n)$ rounds. The number of colors is optimal since at least two colors are required for point robots [G.A. Di Luna, P. Flocchini, S.G. Chaudhuri, F. Poloni, N. Santoro, and G. Viglietta. Mutual visibility by luminous robots without collisions. Information and Computation, 254:392-418, 2017.].
