Improved Fast Algorithms for Optimal Min-Max Line Barrier Coverage with Mobile Sensors on the Plane

Emerging applications raise the min-max line barrier coverage (LBC) problem that aims to minimize the maximum movement of the sensors for the sake of balancing energy consumption. In this paper, we devise an exact algorithm to optimally solve LBC within a runtime of O(n2), comparing favorably to the previous state-of-art runtime O(n2 log n), where n is the number of sensors. To achieve the improvement, we accelerate the computation of optimum solutions by using a novel approximation algorithm. Numerical experiments demonstrated that our algorithms outperform all the other baselines, including the previous state-of-art algorithm.