A local O(n 2 ) gathering algorithm
Bastian Degener, Barbara Kempkes, Friedhelm Meyer auf der Heide · 2010
The gathering problem, where n autonomous robots with restricted capabilities are required to meet in a single point of the plane, is widely studied. We consider the case that robots are limited to see only robots within a bounded vicinity and present an algorithm achieving gathering in O(n2) rounds in expectation. A round consists of a movement of all robots, in random order. All previous algorithms with a proven time bound assume global view on the configuration of all robots.