Bounds on mutual visibility algorithms

摘要

We consider the fundamental Mutual Visibility problem for a set of n identical autonomous point robots (n is not known to the robots) that operate following Look-Compute-Move cycles starting from arbitrary distinct positions in the Euclidean plane under obstructed visibility - a robot ri can see robot rj, rj 6= ri, if and only if there is no other robot in the line segment joining their positions. The objective is to determine a schedule to reposition these robots without collisions such that they reach in finite time a configuration where they all see each other. In the recently proposed so-called robots with lights model, Di Luna et al. [15] gave two deterministic algorithms Contain and Shrink for this problem; however, no runtime bounds were given except the proof that they terminate in finite time. In this paper, we first study the runtime bounds of these algorithms in the fully synchronous setting showing that Contain is tight (-(n) rounds) and Shrink needs (n2) rounds in the worst-case. We then present a new deterministic algorithm, called Modified Shrink, for fully synchronous setting that solves this problem in O(n log n) rounds, improving significantly over Shrink. We also show that Modified Shrink has the lower bound of (n) rounds.