Interference in Random Point Sets
In a geometric graph, $G$, each node $v$ has a transmission radius \[ r(v) = \max\{|vw| : vw\in E(G)\} \] equal to the distance to its furthest neighbour. This defines a transmission disk \[ d(v) = \{ p : |vp|\le r(v)\} \enspace . \] The (receiver-centric) interference at a point $p$ is defined as the number of transmission disks that contain $p$ \[ I_G(p) = |\{v\in V(G):p\in d(v)\}| \enspace , \] and the (maximum receiver-centric) interference of $G$ is \[ I(G) = \max\{I_G(p) : p\in\R^2\} \enspace . \] Finally, the interference of a finite point set $V$ is \[ \min\{I(G):\text{$V(G)=V$ and $G$ is connected}\} \enspace . \]
Devroye and Morin show that $\E[I(V)] \in O(\log^{1/3}n)$ and that $\E[I(V)] \in \Omega(\log^{1/4}n)$.