Minimizing the Maximum Sensor Movement towards Grid Points for Barrier Coverage

Barrier coverage has important applications in military and homeland security. Given a set of mobile sensors and their initial positions, how to move these sensors to achieve the required barrier coverage while maintaining balanced battery consumption across all sensors is a challenging problem of great significance in both theory and applications. Given a set of grid points on the barrier line, a set of sensors located on the plane containing the barrier line, we study the MinMax problem of relocating the sensors to the grid points such that the maximum sensor movement is minimized. In this paper we present an O (n2logn) time algorithm for this problem, which improves the previously known result of O (n3logl) time. Our algorithm deploys a novel decision algorithm that determines whether each grid point can be occupied by a sensor within a given maximum moving distance, and then finds the minimum among these distances using binary search.