Uniform Dispersal of Robots with Minimum Visibility Range

We consider the filling problem, in which autonomous mobile robots enter a connected orthogonal area from several entry points and have to disperse in order to reach full coverage. The entry points are called doors. The area is decomposed into cells. The robots are autonomous, anonymous, they have a limited visibility range of one unit, and do not use explicit communication. Collision of the robots is not allowed. First we describe an algorithm solving the filling problem for the single door case in O(n) time steps in the synchronous model, where n is the number of cells in the area. This algorithm is optimal in terms of visibility range, and asymptotically optimal in running time and size of persistent memory used by the robots. Moreover, we show that our algorithm solves the multiple door filling problem in O(n) time, as well. For the multiple door case, our algorithm is asymptotically worst-case optimal, and its running time is at most k times the running time of the optimal algorithm for any input, where k is the number of doors.