text: The (maximum receiver-centric) interference of a geometric graph (von (2005)) is studied. It is shown that, with high probability, the following results hold for a set, V, of n points independently and uniformly distributed in the unit d-cube, for constant dimension d: (1) there exists a connected graph with vertex set V that has interference O((log n)^ 1 3 ); (2) no connected graph with vertex set V has interference o((log n)^ 1 4 ); and (3) the minimum spanning tree of @math has interference Theta(( n)^ 1 2 ).
  @cite_7: Consider n sensors whose positions are represented by n uniform, independent and identically distributed random variables assuming values in the open unit interval (0; 1). A natural way to guarantee connectivity in the resulting sensor network is to assign to each sensor as its range, the maximum of the two possible distances to its two neighbors. The interference at a given sensor is dened as the number of sensors that have this sensor within their range. In this paper we prove that the expected maximum interference of the sensors is ( p lnn).
summary: log suggests that point sets with very high interference are unlikely to occur in practice. This intuition is born out by the results of Kranakis al @cite_7 , who show that high interference is unlikely to occur in random point sets in one dimension: Note that, in this one-dimensional case, the minimum spanning tree, @math , is simply a path that connects the points of @math in order, from left to right. Taken together, Part 1 of Theorems and generalize sqrtlogn to arbitrary constant dimensions @math .