Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain∗

In this paper, we study the problem of moving n sensors on a line to form a barrier coverage of a specified segment of the line such that the maximum moving distance of the sensors is minimized. Previously, it was an open question whether this problem on sensors with arbitrary sensing ranges is solvable in polynomial time. We settle this open question positively by giving an O(n2 logn log log n) time algorithm. For the special case when all sensors have the same-size sensing range, the previously best solution takes O(n2) time. We present an O(n log n) time algorithm for this case; further, if all sensors are initially located on the coverage segment, our algorithm takes O(n) time. Also, we extend our techniques to the cycle version of the problem where the barrier coverage is for a simple cycle and the sensors are allowed to move only along the cycle. For sensors with the same-size sensing range, we solve the cycle version in O(n) time.