  In recent times, a considerable amount of work has been devoted to the
development and analysis of gossip algorithms in Geometric Random Graphs. In a
recently introduced model termed "Geographic Gossip," each node is aware of its
position but possesses no further information. Traditionally, gossip protocols
have always used convex linear combinations to achieve averaging. We develop a
new protocol for Geographic Gossip, in which counter-intuitively, we use {\it
non-convex affine combinations} as updates in addition to convex combinations
to accelerate the averaging process. The dependence of the number of
transmissions used by our algorithm on the number of sensors $n$ is $n
\exp(O(\log \log n)^2) = n^{1 + o(1)}$. For the previous algorithm, this
dependence was $\tilde{O}(n^{1.5})$. The exponent 1+ o(1) of our algorithm is
asymptotically optimal. Our algorithm involves a hierarchical structure of
$\log \log n$ depth and is not completely decentralized. However, the extent of
control exercised by a sensor on another is restricted to switching the other
on or off.
