Efficient Broadcast on Random Geometric Graphs

A Random Geometric Graph (RGG) in two dimensions is constructed by distributing it, nodes independently and uniformly at random in [0, root n](2) and cleating edges between every pan of nodes having Euclidean distance at most r, for sonic prescribed r We analyze the following randomized broadcast algorithm on RGGs At the beginning, only one node horn the largest, connected component of the RGG is informed Then, in each round, each informed node chooses a. neighbor independently and uniformly at random and informs it We prove that with probability 1 - O(n(-1)) this algorithm informs every node in the largest connected component, of an RGG within O(root n/r + log n) rounds This holds for any value of r larger than the critical value for the emergence of a connected component; with Q(n) nodes. In order to wove this result, we show that for any two nodes sufficiently distant from each other in [0, 0712, the length of the shortest path between them in the RGG, when such a path exists, is only a. constant factor larger than the optimum This result has independent, interest and, in particular, gives that the diameter of the largest; connected component of an RGG is circle minus(root n/r), which surprisingly has been an open problem so far