Probability that there is an edge between two nodes in a random geometric graphI have a graph with vertices being generated uniformly over [ 0 , 1 ] 2 . There is an edge between two vertices if the Euclidean distance between the two vertices is ≤ r. I am trying to find the probability of this. For that I am starting as below: P ( two random nodes have an edge between them ) = P ( ( x i − x j ) 2 + ( y i − y j ) 2 ≤ r 2 )

Question

Probability that there is an edge between two nodes in a random geometric graphI have a graph with vertices being generated uniformly over   [  0  ,  1      ]    2  . There is an edge between two vertices if the Euclidean distance between the two vertices is   ≤  r. I am trying to find the probability of this. For that I am starting as below:  P  (      two random nodes have an edge between them    )  =  P  (  (      x    i    −      x    j        )    2    +  (      y    i    −      y    j        )    2    ≤      r    2    )

Olive Avila · Accepted Answer

Step 1After some hesitations, it seems that one is actually throwing two points uniformly and independently in   [  0  ,  1      ]    2   and that one asks for the probability p(r) that their distance is at most r. Thus,   p  (  r  )  =      ∬          [      0      ,      1              ]        2              A  (  x  ,  r  )        d    x  , where A(x,r) is the area of the set   [  0  ,  1      ]    2    ∩  D  (  x  ,  r  )  , where D(x,r) is the full disk   D  (  x  ,  r  )  =  {  y  ∈            R        2    ∣  ‖  y  −  x  ‖  ⩽  r  }  .Step 2The computation of the exact value of p(r) is tedious (except when   r  ⩾      2   since then   p  (  r  )  =  1 but one can note that, for every   r  ⩽  1, the set   [  0  ,  1      ]    2    ∩  D  (  x  ,  r  ) is at most D(x,r), whose area is   π      r    2  , and at least a quarter of D(x,r). Thus,             1      4        π      r    2    ⩽  p  (  r  )  ⩽  π      r    2    .Recall that this holds only for   0  &amp;lt;  r  ⩽  1.

Open question

Answer & Explanation

New Questions in High school geometry