A
Random Geometric Graph (RGG) in two dimensions is constructed by
distributing
n nodes independently and uniformly at random in [0,
√n]
^{2}
and creating edges between every pair of nodes having Euclidean distance at most
r, for some prescribed
r. We analyze the following randomized broadcast
algorithm on RGGs. At the beginning, only one node from 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(
√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 Ω(
n) nodes. In order to prove
this result, we show that for any two nodes sufficiently distant from each other
in [0,
√n]
^{2}, 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 Θ(
√n/
r),
which surprisingly has been an open problem so far.