Abstract
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.
Original language | English (US) |
---|---|
Pages | 268-274 |
Number of pages | 7 |
State | Published - 2015 |
Externally published | Yes |
Event | 27th Canadian Conference on Computational Geometry, CCCG 2015 - Kingston, Canada Duration: Aug 10 2015 → Aug 12 2015 |
Conference
Conference | 27th Canadian Conference on Computational Geometry, CCCG 2015 |
---|---|
Country/Territory | Canada |
City | Kingston |
Period | 8/10/15 → 8/12/15 |
ASJC Scopus subject areas
- Geometry and Topology
- Computational Mathematics