On time complexity for connectivity-preserving scattering of mobile robots

The scattering problem is a fundamental task for mobile robots, which requires that no two robots share the same position. We investigate the scattering problem in the limited-visibility model. In particular, we focus on the connectivity-preservation property, i.e., the scattering must be achieved so that the disconnection of the visibility graph never occurs (in the visibility graph nodes are robots and edges are their visibility relationship). This paper shows a new scattering algorithm in the semi-synchronous model, which guarantees the connectivity preservation property, and reaches a scattered configuration within O(min⁡{n,D2+log⁡n}) asynchronous rounds in expectation, where n is the number of robots and D is the diameter of the initial visibility graph. Note that a part of this complexity analysis is adaptive in the sense that it depends on D. This implies that our algorithm quickly scatters all robots crowded with a small-diameter visibility graph. We also show two matching lower bounds for the connectivity-preserving scattering problem. The first lower bound is Ω(n) rounds in the case of D=Ω(n), which is a lower bound applying to any connectivity-preserving algorithm. The second bound applies to a (reasonably) restricted class of algorithms, called conservative algorithms, which provides Ω(D2)-round lower bound. These two bounds imply that our algorithm achieves the optimal running time (in the sense of both adaptive and non-adaptive analyses) as conservative ones because it is conservative.