Sublinear-time mutual visibility for fat oblivious robots

摘要

We consider a system of N autonomous mobile robots that operate following the classic oblivious robots model. In particular, we consider fat robots abstracted as unit discs operating on an infinite grid graph G (embedded on the Euclidean plane), and study the fundamental problem, where starting from an arbitrary initial configuration, N autonomous robots reposition themselves on the nodes of G to reach a configuration where each robot is visible to all others (the Complete Visibility problem). We provide the first [MATH HERE]-time algorithm for this problem under a centralized scheduler. We also show that the algorithm is asymptotically tight, i.e., even under a centralized scheduler, any algorithm needs [MATH HERE] time for this problem. We then provide the first [MATH HERE]-time algorithm for this problem under a distributed scheduler for a special initial configuration. To the best of our knowledge, these are the first sublinear-time results for the visibility of fat oblivious robots.