The expected size of some graphs in computational geometry (Q1106021)

Let S be a set of n points in \(E^ d\), the d-dimensional Euclidean space. The Gabriel graph of S connects two points p, \(q\in S\) if the ball with center \((p+q)/2\) and radius \(\| p-q\| /2\) contains no other point of S. The paper shows that the expected number of edges of the Gabriel graph is about \(2^{d-1}\cdot n\) for most densities from which S is chosen. It is at least \(2^{d-1}\cdot n\), when n tends to infinity, for all densities. The relative neighborhood graph of S connects p, \(q\in S\) if no other point of S lies in the intersection of the two balls with radius \(\| p-q\|\) that are centered at p and at q. Also for this graph, which is a subgraph of the Gabriel graph of S, a formula for the expected number of edges depending on n, d, and the density is derived. Both results and some additional results on nearest neighbor graphs are corollaries of a main theorem which gives a lower bound on the expected number of edges for all densities that depends on n, d, and the region used to define the particular graph.