Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Consider a straight highway in the plane which can be modelled by a horizontal strip in the plane. A finite set T of targets are located on the highway, and a finite set S of wireless sensors are located outside of the highway. A sensor s can monitor a target t if and only if the Euclidean distance between s and t is at most one. Suppose that each sensor s is an element of S has a positive cost c (s) and each target t is an element of T can be monitored by at least one sensor in S. Consider a subset S' of sensors in S. S' is said to be a cover if each target in T is covered by at least one sensor in S'. The cost of S' is the total costs of the sensors in S'. The objective is to compute a cover S' of minimum cost. This is a polynomial time algorithm

Consider a 2D plane. There are targets that are randomly distributed between a $y$ upper bound and lower bound. This set is $T$. $T_1$ is marked with coordinates $(X,Y)$. There is a set $S$ of sensors that are guaranteed to cover every target. Each sensor has a radius $1$ and an $(X,Y)$ coordinate. Each target has a cost $c$ that is a weight. So my task is to find a minimum weight or cost for a set $S'$ that covers each sensor.

So I know that there is a recursive relation between the disks that "dominate" or "control" other disks but I'm having trouble seeing a property that shows how to utilize the dominance of the disks. I got this far:

Let $D^+$ be the set of disks whose center lies above the strip (upper disks).

Let $D^-$ be the set of disks whose center lies below the strip (lower disks).

Consider an upper disk $d$, and $d$ intersects a vertical line $L$. Another upper disk $d'$ is said to be controlled or dominated by $d$, if one of the following holds:

  1. $d'$ does not intersect $L$,
  2. the lower intersection endpoint of $d'$ and $L$ is higher than the lower intersection endpoint of $d$ and $L$, and
  3. the lower intersection endpoint of $d'$ and $L$ is identical to the lower intersection endpoint of $d$ and $L$, but the center of $d'$ is on the right of the center of $d$.

Similarly, for a lower disk $d$, and $d$ intersects a vertical line $L$. Another lower disk $d'$ is said to be controlled or dominated by $d$, if one of the following holds:

  1. $d'$ does not intersect $L$,
  2. the upper intersection endpoint of $d'$ and $L$ is lower than the upper intersection endpoint of $d$ and $L$, and
  3. the upper intersection endpoint of $d'$ and $L$ is identical to the upper intersection endpoint of $d$ and $L$, but the center of $d'$ is on the right of the center of $d$.

Howevern, I'm having trouble finalizing the algorithm. Any help? Is that clear?

share|improve this question
    
Would be easier to read if the sentences started with capitals, and you used mathjax (see here). –  Realz Slaw Nov 21 '12 at 22:35
    
I tried to clarify your question. Please check that I didn't change the meaning of it. Also, it might be a good idea to somehow combine the conditions to make the question more readable. –  Juho Nov 22 '12 at 3:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.