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?

  • 6
    $\begingroup$ This reads like a literal copy from an exercise sheet. Please give proper attribution, and include your own thoughts and attempts. $\endgroup$ – Raphael Oct 14 '12 at 13:49
  • $\begingroup$ 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. $\endgroup$ – Bitwise Oct 14 '12 at 16:52
  • $\begingroup$ @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. $\endgroup$ – Raphael Oct 14 '12 at 21:22
  • 1
    $\begingroup$ @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. $\endgroup$ – Bitwise Oct 14 '12 at 22:24
  • $\begingroup$ can you mention some of these greedy algorithms you came up with ? $\endgroup$ – AJed Oct 15 '12 at 12:45

Just observations that do not fit on the comments:

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 [1].

I would suggest you look in the same reference for a solution for the case of equal sensing ranges. So I think a greedy solution exist.

[1] On Minimizing the Maximum Sensor Movement for Barrier Coverage of a Line Segment. J. Czyzowicz , E. Kranakis , D. Krizanc , I. Lambadaris , L. Narayanan , J. Opatrny , L. Stacho , J. Urrutia, and M. Yazdani.

  • 1
    $\begingroup$ It was not asked to cover every point but only to decide if such a cover exists for a given number of finitely many points. Also, my fist impression is, that a greedy algorithm is within reach. $\endgroup$ – A.Schulz Oct 15 '12 at 8:38
  • $\begingroup$ @A.Schulz actually, my first impression is NP-Complete - given the varying interval for each sensor. If they have fixed range, then the idea would be to find the optimal number of sensors to cover the points, using a greedy algorithm. Based on this result, we can decide. --> but dont take this answer for granted. it is only a comment. $\endgroup$ – AJed Oct 15 '12 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.