We are given an interval $I$ and several points $p_1,p_2,...,p_n$. We are also given a set of sensors. Each sensor can be represented by an interval on the same line, which means all points lie within the interval can be monitored by the corresponding sensor. The sensors may not have the equal range.Given the current positions of points and sensors, some (or maybe none) points in $I$ may not be monitored by any sensor. We would like to ask the following question: Given a distance $\delta$, is it possible to shift each sensor (to the left or to the right) by a distance at most $\delta$, such that every point in $I$ can be covered by some sensor?PS: I tried to solve this by greedy algorithm. But there is always an exception to any greedy paradigm I came up with. If we want to cover the whole interval with the sensors, I am sure it can be solved by greedy algorithm. But if we only want to monitor finite discrete points, is there an efficient algorithm?
Sensor Cover Problem
algorithms;computational geometry