@inproceedings{63d9fd95b18549418d94fd227f7a5ae8,
title = "Logarithmic-Time Complete Visibility for Robots with Lights",
abstract = "We consider the problem of repositioning N autonomous robots on a plane so that each robot is visible to all others (the Complete Visibility problem), a robot cannot see another robot if there Isa third robot positioned between them on the straight line joining them. Robots communicate using collared lights. The computation is synchronous and each robot performs a look-compute-move during a round. Specifically, during a round a robot is permitted to observe the light and position of every robot visible to it. It may also perform an internal computation based on the observed lights and positions(including deciding on a new-collar for its own light), and possibly moving to a new position at the end of the round. The challenge posed by this model of computation stems from the fact that each robot has only a constant number of colours for its lights(symbols for communication) and no memory(except for the persistence of lights) between rounds. In this paper we first show that the best previously known algorithm for the complete visibility problem on this model runs in linear time in the worst case. We then present the first logarithmic time complexity algorithm for Complete Visibility. The model we assume use sterility, is fully-synchronous and allows robot paths to cross.",
keywords = "Convex hull, Distributed algorithms, Mobile robots, Robots with lights, Visibility",
author = "Ramachandran Vaidyanathan and Costas Busch and Trahan, {Jerry L.} and Gokarna Sharma and Suresh Rai",
year = "2015",
month = jul,
day = "17",
doi = "10.1109/IPDPS.2015.52",
language = "English (US)",
series = "Proceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium, IPDPS 2015",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "375--384",
booktitle = "Proceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium, IPDPS 2015",
note = "29th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015 ; Conference date: 25-05-2015 Through 29-05-2015",
}