Given @math intervals on a line @math , we consider the problem of moving these intervals on @math such that no two intervals overlap and the maximum moving distance of the intervals is minimized. The difficulty for solving the problem lies in determining the order of the intervals in an optimal solution. By interesting observations, we show that it is sufficient to consider at most @math "candidate" lists of ordered intervals. Further, although explicitly maintaining these lists takes @math time and space, by more observations and a pruning technique, we present an algorithm that can compute an optimal solution in @math time and @math space. We also prove an @math time lower bound for solving the problem, which implies the optimality of our algorithm.
Many problems on wireless sensor networks are also modeled as interval problems. For example, a mobile sensor barrier coverage problem can be modeled as the following interval problem. Given on a line @math intervals (each interval is the region covered by a sensor at the center of the interval) and another segment @math (called barrier''), the goal is to move the intervals such that the union of the intervals fully covers @math and the maximum moving distance of all intervals is minimized. If all intervals have the same length, @cite_8 solved the problem in @math time and later @cite_18 improved it to @math time. If intervals have different lengths, @cite_18 solved the problem in @math time. The min-sum version of the problem has also been considered. If intervals have the same length, @cite_21 gave an @math time algorithm, and Andrews and Wang @cite_15 solved the problem in @math time. If intervals have different lengths, then the problem becomes NP-hard @cite_18 . Refer to @cite_9 @cite_13 @cite_17 @cite_16 @cite_14 @cite_1 for other interval problems on mobile sensor barrier coverage.
@cite_18 @cite_14 @cite_8 @cite_9 @cite_21 @cite_1 @cite_15 @cite_16 @cite_13 @cite_17
2949632354 1988777116 1817887473 2217656054
We consider an interval coverage problem. Given @math intervals of the same length on a line @math and a line segment @math on @math , we want to move the intervals along @math such that every point of @math is covered by at least one interval and the sum of the moving distances of all intervals is minimized. As a basic geometry problem, it has applications in mobile sensor barrier coverage in wireless sensor networks. The previous work solved the problem in @math time. In this paper, by discovering many interesting observations and developing new algorithmic techniques, we present an @math time algorithm. We also show an @math time lower bound for this problem, which implies the optimality of our algorithm. In this paper, we study the problem of moving @math 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 @math O(n2logn) time algorithm. For the special case when all sensors have the same-size sensing range, the previously best solution takes @math O(n2) time. We present an @math O(nlogn) time algorithm for this case; further, if all sensors are initially located on the coverage segment, our algorithm takes @math 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 @math O(n) time, improving the previously best @math O(n2) time solution. 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(n2lognloglogn) time algorithm. Further, if all sensors have the same-size sensing range, we give an O(nlogn) time algorithm, which improves the previous best O(n2) time solution. We consider several variations of the problems of covering a set of barriers (modeled as line segments) using sensors that can detect any intruder crossing any of the barriers. Sensors are initially located in the plane and they can relocate to the barriers. We assume that each sensor can detect any intruder in a circular area centered at the sensor. Given a set of barriers and a set of sensors located in the plane, we study three problems: the feasibility of barrier coverage, the problem of minimizing the largest relocation distance of a sensor (MinMax), and the problem of minimizing the sum of relocation distances of sensors (MinSum). When sensors are permitted to move to arbitrary positions on the barrier, the problems are shown to be NP-complete. We also study the case when sensors use perpendicular movement to one of the barriers. We show that when the barriers are parallel, both the MinMax and MinSum problems can be solved in polynomial time. In contrast, we show that even the feasibility problem is NP-complete if two perpendicular barriers are to be covered, even if the sensors are located at integer positions, and have only two possible sensing ranges. On the other hand, we give an O(n 3 2) algorithm for a natural special case of this last problem.