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

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