Mutual Visibility with an Optimal Number of Colors

We consider the following fundamental Mutual Visibility problem: Given a set of n identical autonomous point robots in arbitrary distinct positions in the Euclidean plane, find a schedule to move them such that within finite time they reach, without collisions, a configuration in which they all see each other. The robots operate following Look-Compute-Move cycles and a robot \(r_i\) can not see other robot \(r_j\) if there lies a third robot \(r_l\) in the line segment connecting the positions of \(r_i\) and \(r_j\). Moreover, n is not assumed to be known to the robots. We study this problem in the robots with lights model, where each robot has an externally visible persistent light which can assume colors from a fixed set of colors and the color set is identical to all the robots. This model corresponds to the classical model of oblivious robots when the number of colors \(c=1\) in the color set. Therefore, we focus here on the objective of minimizing the number of colors required to successfully solve Mutual Visibility. Di Luna et al. [16] presented two algorithms and showed that Mutual Visibility can always be solved without collisions with \(c=3\) colors for both semi-synchronous and asynchronous robots under both rigid and non-rigid moves. In this paper, we present and analyze an improved algorithm which requires only \(c=2\) colors and works for both semi-synchronous and asynchronous robots under both rigid and non-rigid moves; this is optimal since any algorithm for Mutual Visibility needs at least 2 colors in the robots with lights model, when n is not known. We employ a non-trivial technique which moves all the interior robots first to the boundary of the initial convex hull and then the robots in the boundary of the hull (except the corners) to outside of the hull until all the robots eventually become corners, without the need of any third color. Our result is interesting in the sense that asynchronicity and non-rigidity of robot movements have no effect on Mutual Visibility with respect to the number of colors needed to successfully solve it. We also provide an improved solution to the Circle Formation problem.