# Sensor Cover Problem

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?

• This reads like a literal copy from an exercise sheet. Please give proper attribution, and include your own thoughts and attempts. – Raphael Oct 14 '12 at 13:49
• Seems like you are missing some information on the sensors, as in how much they cover. For example, if each sensor covers a region of the size |I|/10 and you have 5 sensors, there is no way you can cover all of I. – Bitwise Oct 14 '12 at 16:52
• @Bitwise That seems to be covered by "Each sensor can be represented by an interval on the same line", that is each sensor has it's own range. – Raphael Oct 14 '12 at 21:22
• @Raphael I am just saying that for some combinations of ranges like the case I specified, this task is obviously impossible regardless of $\delta$. Perhaps I could have worded it better. – Bitwise Oct 14 '12 at 22:24
• can you mention some of these greedy algorithms you came up with ? – AJed Oct 15 '12 at 12:45

I made a little research, and here are what I found + some of my observations: 1) You can use exhaustive search to find whether a solution exist. [so it is decidable] 2) In case $\delta$ is not restricted, all you need to check is the sum of all ranges and compare it to the distance between the farthest two points. If greater or equal, then there exist a solution. 3) In case $\delta$ is restricted, then you are trying to restrict the distance traveled by sensors to at most $n \delta$. In case the sensing ranges are not equal, then this problem is still open .