ON THE VARIANCE OF THE RANDOM SPHERE OF INFLUENCE GRAPH§

P. Hitczenko*^{†}, S. Janson^{†}, and J.E. Yukich^{‡}

Abstract. We show that the variance of the number of edges in the random sphere of influence graph built on n i.i.d. sites which are uniformly distributed over the unit cube in R^{d}, grows linearly with n. This is then used to establish a central limit theorem for the number of edges in the random sphere of influence graph built on a Poisson number of sites. Some related proximity graphs are discussed as well.

1. Introduction. The main focus of this paper is to find a growth rate on the variance of the number of edges in the sphere of influence graph. These graphs have been introduced by Toussaint [15] and, according to specialists in pattern recognition, perform better than previously used proximity graphs. Let X_{1}, …, X_{n} be i.i.d. random variables uniformly distributed on the unit cube in R^{d}, d ≥ 2. We will call these points sites. The random sphere of influence graph is constructed as follows: for each i, let B_{i} be a ball around X_{i} with radius equal to min{|X_{i} − X_{j}| : i ≠ j} (i.e. the distance from X_{i} to its closest neighbor). This ball is often called the sphere of influence of X_{i}. We draw an edge between X_{j} and X_{k} if and only if the balls B_{j} and B_{k} overlap. The quantity of interest is the total number of edges in the graph. We call this the size of the graph and denote it by e, e_{n}, or e(X_{1}, …, X_{n}). It is known that we always have c_{d}n ≤ Ee ≤ C_{d}n for some absolute positive constants c_{d} and C_{d} (we refer the reader to the survey paper [10] for detailed references on this result). Füredi [7] showed that Ee/n has a limit as n → ∞ and identified the value of that limit (in the case d = 2, the limiting value is 1 + π/4.) The same result was later obtained by Chalker et al. in [3]. The authors of the latter paper also found a bound on the tail probability of the deviation of the size of sphere of influence graph from its mean. Fluctuations results are a bit more difficult because the sphere of influence graph does not have very good regularity properties: in certain configurations, relocating just one site can lead to a significant change in the number of edges. (This is seen by considering the following situation: if n − 1 sites are regularly spaced on a circle, and the last site is near the center of that circle, then it is incident to all n − 1 remaining sites; if it is moved to the boundary of the circle its degree becomes bounded independently of n. Changes in the degrees of other sites are insignificant.)

§ This is a preprint of an article accepted for publication in Random Structures and Algorithms \begin{matrix}c \\ ◯ \end{matrix} John Wiley & Sons, Inc.

* Supported in part by NSF grant DMS 9401345

† part of the research of these authors was done while they were in residence at the meeting Random Graphs and Combinatorial Structures in Oberwolfach, October 1997

‡ Supported in part by NSA grant MDA 904–97–1–0053 AMS 1991 Subject Classification: 60C05, 60D05, 60E15, 05C80, 60G42

This paper concentrates mainly on finding the upper and lower bounds on the variance of the size of the sphere of influence graph. We will show that the variance grows linearly in n, the total number of sites.

Theorem 1. Let e_{n} be the number of edges in the sphere of influence graph built on n i.i.d. sites uniformly distributed over [0, 1]^{d}. Then there exist absolute positive constants, c_{d} and C_{d} such that for any n ≥ 4

c_{d}n ≤ var(e_{n}) ≤ C_{d}n.

The proof of the upper bound is based on the Efron – Stein inequality and will be given in the next section. The lower bound follows a technique developed by Avram and Bertsimas [1], and we will give the details in section 3.

One consequence of our variance bound is the fact that, at least if we consider a Poisson distributed number of points, the total number of edges, normalized in the usual way, satisfies the central limit theorem. As it turns out, our methods give upper bounds on higher moments, and work for some related proximity graphs as well. We will discuss some of these results briefly in the last section. Throughout the paper, the constants (denoted by various letters) are always absolute. They can possibly depend on d which is considered arbitrary, but fixed. The value of a constant may change from line to line. The volume of the unit ball in R^{d} is denoted by v_{d}.

2. Upper bound for the variance. Given the sites X_{1}, …, X_{n}, let D(X_{i}) be the degree of a vertex X_{i} (i.e. the number of edges incident to X_{i}) in the sphere of influence graph. The general approach uses the Efron – Stein inequality, along the same lines as in Steele [14], Section 6. To this end, let us denote by e_{i}^{∗} the size of the graph with the ith observation withheld, i.e.

e_{i}^{∗} = e(X_{1}, …, X_{i−1}, X_{i+1}, …, X_{n}).

We wish to apply the Efron – Stein inequality [6], which says that

var(e_{n−1}) = var(e_{n}^{∗}) ≤ E ∑_{i=1}^{n} (e_{i}^{∗} − \frac{1}{n} ∑_{j=1}^{n} e_{j}^{∗})^{2} .

Since the average minimizes the sum under the above expectation, it can be replaced by

any other quantity, for example by e. Thus, we will need an upper bound on E ∑_{i=1}^{n}(e_{i}^{∗}−e)^{2}.

To this end, first observe that adding a new site creates new edges (incident to that site) and may remove edges between old sites, but cannot create any new edges between two old sites. Therefore,

e − e_{i}^{∗} ≤ D(X_{i}).

We will now estimate e_{i}^{∗} − e. Let

N(X_{i}) = {j ≤ n, j ≠ i : |X_{j} − X_{i}| ≤ |X_{j} − X_{k}|, k ≠ i}

be the (possibly empty) set of (indices) of sites for which X_{i} is the nearest neighbor. Consider e and suppose that X_{i} is removed. Then, every site for which X_{i} was the nearest neighbor will have to find a new nearest neighbor. As a result, its new sphere of influence will have a larger radius, and may therefore intersect other spheres, causing an increase in the total number of edges. However, for each such site, say X_{j}, the increase cannot be more than the degree of X_{j} in the random sphere of influence graph with vertex i withheld. Let us denote this degree by D_{i}(X_{j}). Then we can write

e_{i}^{∗} ≤ e + ∑_{j∈N(X_{i})} D_{i}(X_{j}),

i.e.

e_{i}^{∗} − e ≤ ∑_{j∈N(X_{i})} D_{i}(X_{j}).

Combining this with the previous estimate we obtain

(e_{i}^{∗} − e)^{2} ≤ D^{2}(X_{i}) + ( ∑_{j∈N(X_{i})} D_{i}(X_{j}))^{2} .

By the Cauchy – Schwarz inequality the rightmost term can be bounded above by

D^{2}(X_{i}) + |N(X_{i})| ∑_{j∈N(X_{i})} D_{i}^{2}(X_{j}),

where |N(X_{i})| denotes the cardinality of N(X_{i}). It is easy to see [3] that |N(X_{i})| ≤ K_{d}, where K_{d} is a constant depending only on the dimension d. Thus taking expectations, we infer that

\begin{aligned}var(e_{n}^{∗}) & ≤ ∑_{i=1}^{n} E (D^{2}(X_{i}) + K_{d} ∑_{j∈N(X_{i})} D_{i}^{2}(X_{j})) \\ & = nE (D^{2}(X_{1}) + K_{d} ∑_{j∈N(X_{1})} D_{1}^{2}(X_{j})) , \end{aligned}

since the random variables in question are identically distributed. Thus the proof will be complete once we show that

ED^{2}(X_{1}) ≤ C,

and

E ∑_{j∈N(X_{1})} D_{1}^{2}(X_{j}) ≤ C.

As we will see below, the first estimate follows from the proof of the second so we concentrate on the second bound. To this end, let I_{j} be the indicator of the event that the nearest neighbor of X_{j} is X_{1}. Further, let G be the σ-algebra generated by X_{2}, …, X_{n}. Then we have

E ∑_{j∈N(X_{1})} D_{1}^{2}(X_{j}) = ∑_{j=2}^{n} E (I_{j}D_{1}^{2}(X_{j})) = ∑_{j=2}^{n} E (D_{1}^{2}(X_{j})E(I_{j}|G)) .

Denote by p_{j} the conditional expectation E(I_{j}|G). Using Hölder’s inequality, we see that the sum above can be bounded above by

∑_{j=2}^{n}(ED_{1}^{3}(X_{j}))^{2/3}(Ep_{j}^{3})^{1/3}.

Thus, in order to complete this part of the proof, it suffices to show that Ep_{j}^{3} ≤ C/n^{3} and ED_{1}^{3}(X_{j}) = ED_{1}^{3}(X_{2}) ≤ C.

In order to justify the second statement (which we will do for D(X_{1}) rather than D_{1}(X_{2}) in order to simplify notation), let I_{i,j} be the event that there is an edge between sites X_{i} and X_{j}, and for simplicity we will denote its indicator by the same symbol.

Then we have

ED^{3}(X_{1}) = E (∑_{j=2}^{n} I_{1,j})^{3} = E ∑_{2≤i,j,k≤n} I_{1,i}I_{1,j}I_{1,k}
= (n − 1)P(I_{1,2}) + 3(n − 1)(n − 2)P(I_{1,2} ∩ I_{1,3})
+ (n − 1)(n − 2)(n − 3)P(I_{1,2} ∩ I_{1,3} ∩ I_{1,4}).

It was shown in [5] (or in [3]) that P(I_{1,2}) ≈ c_{d}/n for a constant c_{d} depending only on d. So, it remains to show that P(I_{1,2} ∩ I_{1,3}) ≤ \frac{c_{d}}{n^{2}} and P(I_{1,2} ∩ I_{1,3} ∩ I_{1,4}) ≤ \frac{c_{d}}{n^{3}} . Since both computations are essentially the same, we will present only the second one. We also note that the first inequality implies that ED^{2}(X_{1}) ≤ C.

Let P_{t_{2},t_{3},t_{4}}( ·) be the conditional probability given that |X_{1}−X_{2}| = t_{2}, |X_{1}−X_{3}| = t_{3}, and |X_{1} − X_{4}| = t_{4}. Then, by symmetry

P(I_{1,2} ∩ I_{1,3} ∩ I_{1,4}) = 3! ∫_{0<t_{2}<t_{3}<t_{4}} P_{t_{2},t_{3},t_{4}}(I_{1,2} ∩ I_{1,3} ∩ I_{1,4})f_{2,3,4}(t_{2}, t_{3}, t_{4})dt_{2}dt_{3}dt_{4},

where f_{2,3,4} is the joint density of the distances between X_{1} and X_{2}, X_{1} and X_{3}, and X_{1} and X_{4}.

In the computation below, the statement “B_{r}(X_{j}) is empty” means that no other site is contained in a ball with radius r centered at X_{j}. If the distance between X_{1} and X_{4} is t_{4}, and there is an edge between those two sites, then one of the balls B_{t_{4}/2}(X_{1}) or B_{t_{4}/2}(X_{4}) must be empty. It follows that

\begin{matrix}P & _{t_{2},t_{3},t_{4}}(I_{1,2} ∩ I_{1,3} ∩ I_{1,4}) ≤ P_{t_{2},t_{3},t_{4}}(I_{1,4}) \\ ≤ P_{t_{2},t_{3},t_{4}} (\{B_{t_{4}/2}(X_{1}) = ∅\} ∪ \{B_{t_{4}/2}(X_{4}) = ∅\}) . \end{matrix}

Now, B_{t_{4}/2}(X_{1}) or B_{t_{4}/2}(X_{4}) is empty means that one of these balls contains none of the remaining n − 4 points. It follows that this last probability is no more than (assuming as we may that t_{4} < \sqrt{d})

2 (1 − c_{d}(\frac{t_{4}}{2} )^{d})^{n−4} ,

where c_{d} > 0. If t_{4} > t_{3} > t_{2}, then t_{4}^{d} ≥ (1/3)(t_{4}^{d} + t_{3}^{d} + t_{2}^{d}), and using the inequality 1 − x ≤ e^{−x} we see that the quantity above does not exceed

2 exp \{ − \frac{(n − 4)c_{d}}{2^{d}} t_{4}^{d}\} ≤ 2 exp \{ − \frac{(n − 4)c_{d}}{3 · 2^{d}} (t_{4}^{d} + t_{3}^{d} + t_{2}^{d})\}.

Substituting this quantity in the integral above, and noting that (by conditioning on X_{1}) f_{2,3,4}(t_{2}, t_{3}, t_{4}) ≤ c_{d}t_{2}^{d−1}t_{3}^{d−1}t_{4}^{d−1}, we find that

P(I_{1,2} ∩ I_{1,3} ∩ I_{1,4})

≤ c_{d} ∫_{0<t_{2}<t_{3}<t_{4}} exp \{ − \frac{(n − 4)c_{d}}{3 · 2^{d}} (t_{2}^{d} + t_{3}^{d} + t_{4}^{d})\}t_{2}^{d−1}t_{3}^{d−1}t_{4}^{d−1}dt_{2}dt_{3}dt_{4}

≤ c_{d} (∫_{0}^{∞} exp \{ − \frac{(n − 4)c_{d}}{3 · 2^{d}} t^{d}\}t^{d−1}dt)^{3}

= \frac{c_{d}}{(n − 4)^{3}} ,

as desired.

Finally, to obtain an upper bound on Ep_{j}^{3}, we note that since p_{j} is equal to the volume of the intersection of the unit cube and the sphere of influence about X_{j} (in e_{1}^{∗}), and denoting this sphere by SIG_{1}(X_{j}) and its radius by r_{SIG_{1}(X_{j})}, we see that

Ep_{j}^{3} ≤ Evol^{3}(SIG_{1}(X_{j})) = v_{d}^{3}Er_{SIG_{1}(X_{j})}^{3d} = 3dv_{d}^{3} ∫_{0}^{√\overline{d}} r^{3d−1}P(r_{SIG_{1}(X_{j})} ≥ r)dr,

and since (for r ≤ \sqrt{d})

P(r_{SIG_{1}(X_{j})} ≥ r) ≤ C(1 − c_{d}r^{d})^{n−2} ≤ exp{−c_{d}r^{d}(n − 2)},

it follows that Ep_{j}^{3} ≤ C/n^{3}.

3. Lower bound for the variance. To obtain the lower bound we will use a technique developed by Avram and Bertsimas [1], see also Steele [13], Section 5.8. It is convenient to change our notation; let S be a subset of [0, 1]^{d}, and denote by e(S) the sum of the degrees of vertices contained in S. (Note that, if both endpoints of an edge are contained in S, this edge is counted twice.) Therefore, we have e([0, 1]^{d}) = 2e, and if S_{1}, … S_{k} are pairwise disjoint subsets of [0, 1]^{d} then

e( ⋃_{j=1}^{k} S_{j}) = ∑_{j=1}^{k} e(S_{j}).

Let ℓ = ⌈n^{1/d}⌉ and subdivide [0, 1]^{d} into n_{1} = ℓ^{d} congruent subcubes Q_{1}, …, Q_{n_{1}} with edge length 1/ℓ. Let m_{d} = 4(1 + ⌈\sqrt{d}⌉) + 1 and subdivide each subcube into congruent subcubes with edge length ε = 1/m_{d}ℓ (so that Q_{i} is subdivided into m_{d}^{d} cubes). Let C_{i} be the cube in the center of Q_{i} and for each 1 ≤ i ≤ n_{1} let A_{i} be the event that:

(i) C_{i} contains exactly 4 of the sites X_{1}, …, X_{n}, (ii) each of the m_{d}^{d} − (m_{d} − 2)^{d} subcubes of Q_{i} sharing a face with the boundary of Q_{i}

contains exactly one site, and (iii) the remainder of the cube Q_{i} contains no more sites. Since there are n sites and the volume of each of the subcubes of Q_{i} is proportional to 1/n, P(A_{i}) ≥ α_{d}, where α_{d} is a positive number not depending on n. In particular,

E ∑_{i=1}^{n_{1}} I_{A_{i}} ≥ α_{d}n. Moreover, m_{d} is chosen large enough so that on the event A_{i} the four

sites inside C_{i} have edges only among themselves. Let G be the σ-algebra generated by everything except the location of the four sites within C_{i}, for those C_{i} for which A_{i} occurs. That is, if J(ω) = {j : ω ∈ A_{j}}, then

G = σ {J, {X_{1}, …, X_{n}} ⋂ ( ⋃_{j∈J} C_{j})^{c}} .

Since for any random variable Y and any σ - algebra F we have

var(Y) = var(E_{F}Y) + Evar_{F}(Y),

where var_{F}(Y) = E_{F}(Y − E_{F}Y)^{2}, we have

4var(e) = 4var(E_{G}(e)) + 4Evar_{G}(e)

≥ 4Evar_{G}(e) = Evar_{G} (∑_{i=1}^{n} e(C_{i}))

= Evar_{G} (∑_{i∈J} e(C_{i}) + ∑_{i∉J} e(C_{i}))

= Evar_{G} (∑_{i∈J} e(C_{i})) ,

where the last equality follows from the fact that ∑_{i∉J} e(C_{i}) is G - measurable and that the

variance is translation invariant. Further, given G, the random variables e(C_{i}), i ∈ J, are independent. Therefore,

Evar_{G} (∑_{i∈J} e(C_{i})) = E ∑_{i∈J} var_{G}e(C_{i}).

Conditionally on G, for i ∈ J, the sphere of influence graph built on the four sites that are contained in C_{i} can have 2, 3, 4, 5, or 6 edges, each with positive probability. Moreover, the number of edges depends only on the location of those four sites within C_{i}, and thus is independent of n. Consequently, var_{G}e(C_{i}) ≥ c, for some constant c not depending on n, and therefore,

E ∑_{i∈J} var_{G}e(C_{i}) ≥ cE ∑_{i=1}^{n} I_{A_{i}} ≥ cα_{d}n.

Putting all of these estimates together gives

var(e) ≥ cn,

for some absolute constant c.

4. Remarks. This section contains some consequences and results related to Theorem 1. Perhaps the most significant one is a central limit theorem for the size of the random sphere of influence graph built on a Poisson number of points. It seems reasonable to conjecture that the CLT holds for a nonrandom number of sites, but we have not established that. We begin with the CLT and we will discuss higher moments and other proximity graphs later in this section.

(i) Central limit theorem for the size of the sphere of influence graph. In what follows we use the variance bounds of Theorem 1 and the local behavior of the sphere of influence graph to establish the following result (throughout N(n) denotes a Poisson random variable with parameter n, independent of all other random variables under consideration, and in order to emphasize the dependence on n we will write in this section e_{n} = e(X_{1}, ..., X_{n}).)

Theorem 2. (CLT for the number of edges in the sphere of influence graph) We have

\frac{e_{N(n)} − Ee_{N(n)}}{var^{1/2}(e_{N(n)})} ⟹ N(0, 1),  as  n → ∞.

The local behavior is formalized through the notion of dependency graphs, an idea used by Avram and Bertsimas [1] to establish the asymptotic normality of the length of the k-nearest neighbor graph on a random sample as well as the length of the Delaunay and Voronoi tessellations on a random sample. This approach is also discussed in Steele [13, Sections 5.7, 5.8] and Yukich [16, Section 8.3]. The underlying idea is as follows: subdivide [0, 1]^{d} into Cn/ log n subcubes of edge length C(log n/n)^{1/d}. Consider the high probability event that all subcubes contain at least one point and at most C log n points. Then, conditionally on this event, the sphere of influence graph around a point is determined by only a finite number of the neighboring subcubes. Consequently, the number of edges in the sphere of influence graph satisfies “m-dependence” and thus a central limit theorem, by the theory of dependency graphs (see Baldi and Rinott [2], Janson [9], Petrovskaya and Leontovich [11]). To formalize this discussion, let us recall that if V is a collection of vertices (but not necessarily points in R^{d}) and {Y_{i}} random variables, then the graph G = (V, E) is a dependency graph for the family {Y_{i}} of random variables if the following two conditions are satisfied:

(i) {Y_{i}} are indexed by the vertex set V, (ii) if V_{1} and V_{2} are two disjoint sets of vertices of G such that no edge E of G has one

endpoint in V_{1} and the other in V_{2}, then the sets of random variables {Y_{i}}_{i∈V_{1}} and {Y_{i}}_{i∈V_{2}} are independent.

We then have

Theorem 3. (Baldi and Rinott, [2]) Let {Y_{ni}, i ∈ V_{n}} be random variables with a dependency graph G_{n} = (V_{n}, E_{n}). Let S_{n} = ∑_{i∈V_{n}} Y_{ni}, σ_{n}^{2} := varS_{n} < ∞. Let D_{n} denote the maximum degree of G_{n} and suppose that |Y_{ni}| ≤ B_{n} a.s. for all i ∈ V_{n}. Then for all x ∈ R we have

|P (\frac{S_{n} − ES_{n}}{σ_{n}} ≤ x) − P(N(0, 1) ≤ x)| ≤ 32(1 + 6^{1/2})(\frac{card(V_{n})D_{n}^{2}B_{n}^{3}}{σ_{n}^{3}} )^{1/2}.

To apply Theorem 3 to the random variables e_{N(n)} we subdivide [0, 1]^{d} into m subcubes Q_{1}, ..., Q_{m} of edge length s ≈ K(log n/n)^{1/d}, where K is a large constant to be chosen later. For all 1 ≤ i ≤ m let N_{i} = \frac{1}{2}e(Q_{i}). This evidently yields the decomposition

e_{N(n)} = ∑_{i=1}^{m} N_{i}.

Let n_{i}, 1 ≤ i ≤ m, denote the number of points falling in subcube Q_{i}. Since each n_{i}, 1 ≤ i ≤ m, is a Poisson random variable with parameter ≈ K^{d} log n, it follows that if

A_{n} := ⋂_{i=1}^{m}{1 ≤ n_{i} ≤ K′ log n},

then A_{n} is a high probability event, namely for every α > 0 there are K = K(α) and K′ = K′(α) such that

P(A_{n}) ≥ 1 − n^{−α}.

We now fix K := K(α) and K′ := K′(α) with α = 5, say.

We next define a distance function on sets of subcubes as follows: if A = ⋃_{i∈A} Q_{i} and B = ⋃_{i∈B} Q_{i} for subsets A and B of {1, 2, ..., m}, then

d(A, B) = d_{H}(A, B)/s,

where d_{H} denotes the usual Hausdorff distance. (This distance essentially measures the width of the “moat” separating two collection of subcubes where the common unit of measurement is the edge length of a subcube.) We now make the key observation that conditionally on A_{n}, the sphere of influence around any point has radius at most \sqrt{d + 3}s; hence neighbors in the sphere of influence graph have distance at most 2\sqrt{d + 3}s, and the degree of a site depends only on the location of the sites with a distance less than 3\sqrt{d + 3}s. Thus, if A = ⋃_{i∈A} Q_{i} and B = ⋃_{i∈B} Q_{i} satisfy d(A, B) > 6\sqrt{d + 3}, then conditionally on A_{n} the sets of random variables

{N_{i}, i ∈ A} and {N_{i}, i ∈ B}

are independent.

Define the random variable Y_{i} to be N_{i}, conditioned on the event A_{n}. We now define a dependency graph G_{n} := (V_{n}, E_{n}) as follows. Let V_{n} consist of the m subcubes Q_{1}, ..., Q_{m}. Say that the edge E = (V_{i}, V_{j}), 1 ≤ i, j ≤ m, belongs to E_{n} if and only if d(Q_{i}, Q_{j}) ≤ 6\sqrt{d + 3}. By the argument above, G_{n} is a dependency graph for \{Y_{i}\} (although not for the unconditioned variables N_{i}).

The maximal degree D_{n} of G_{n} satisfies D_{n} ≤ K_{d}. Moreover, given the event A_{n} we have

N_{i} ≤ C log n, 1 ≤ i ≤ m,

and thus Y_{n} ≤ B_{n} := C log n. Moreover, Theorem 1 and the identity

var(e_{N(n)}) = var(E_{σ(N(n))}(e_{N(n)})) + Evar_{σ(N(n))}(e_{N(n)})

imply that

σ_{n}^{2} = var(e_{N(n)}) ≥ cn,

where σ(N(n)) denotes the σ-algebra generated by N(n). Since P(A_{n}) ≥ 1−n^{−5}, it follows easily that the variance of e_{N(n)} conditioned on A_{n} equals var(e_{N(n)}) + o(1) ≥ cn. Thus, by Theorem 3 we have established that conditionally on the event A_{n}, Z_{n} := (e_{N(n)}n − Ee_{N(n)})/(var(e_{N(n)}))^{1/2} converges to a normal N(0, 1) random variable. Finally, it follows that Z_{n} converges unconditionally to a N(0, 1) random variable by taking limits as n → ∞ in the expression

P {Z_{n} ≤ x} = P {Z_{n} ≤ x|A_{n}}P {A_{n}} + P {Z_{n} ≤ x|A_{n}^{c}}P {A_{n}^{c}}

and using the fact that P {A_{n}} → 1 as n → ∞. This proves Theorem 2.

(ii) Higher moments of degrees. Although it is not needed in this paper, it is perhaps worth recording that our method can be used to get bounds for higher moments of the degrees of the vertices in the sphere of influence graph. Indeed, we have Proposition 4. For some constants C_{d}, c_{d} we have for all k ≥ 1,

(a) ∥D(X_{1})∥_{k} ≤ C_{d}k,

(b) Ee^{c_{d}D(X_{1})} ≤ 2 and thus P(D(X_{1}) ≥ k) ≤ 2e^{−c_{d}k}.

Proof: (a) We have

ED^{k}(X_{1}) = E { ∑_{2≤i_{1},...,i_{k}≤n} I_{1,i_{1}} · . . . · I_{1,i_{k}} } = ∑_{j=1}^{k} K_{n−1,j}P(I_{1,2} ∩ … ∩ I_{1,j+1}),

where K_{n−1,j} is the number of terms I_{1,i_{1}} · . . . · I_{1,i_{k}} such that exactly j of the i_{m}’s are distinct. It can, of course, be computed exactly, but for our purposes it is enough to know that K_{n−1,j} ≤ \binom{n−1}{j}j^{k}. (This is, in fact, the correct order.) So we get

ED^{k}(X_{1}) ≤ ∑_{j=1}^{k} \binom{n − 1}{j}j^{k}P(I_{1,2} ∩ … ∩ I_{1,j+1}).

With analogous notation as before we have, for n ≥ 2j + 2 and G = {0 < t_{2} < … < t_{j+1}},

P(I_{1,2} ∩ … ∩ I_{1,j+1})

≤ j! ∫_{G} P_{t_{2},...,t_{j+1}} ({B_{t_{j+1}/2}(X_{1}) = ∅} ∪ {B_{t_{j+1}/2}(X_{j+1}) = ∅}) f_{t_{2},...,t_{j+1}}dt_{2} … dt_{j+1}

≤ 2j! ∫_{G}(1 − c_{d}(t_{j+1}/2)^{d})^{n−(j+1)}f_{t_{2},...,t_{j+1}}dt_{2} … dt_{j+1}

≤ j!c_{d}^{j} ∫_{G} exp \{ − \frac{(n − j − 1)c_{d}}{j · 2^{d}} (t_{2}^{d} + … + t_{j+1}^{d})\}t_{2}^{d−1} … t_{j+1}^{d−1}dt_{2} … dt_{j+1}

= (\frac{c_{d}j}{n − j − 1})^{j} ≤ (\frac{c_{d}j}{n} )^{j} .

For n ≤ 2j + 1 we have the same estimate, since trivially

P(I_{1,2} ∩ … ∩ I_{1,j+1}) ≤ 1 ≤ (\frac{3j}{n} )^{j} .

These give, since j! > j^{j}e^{−j} by Stirling’s formula,

ED^{k}(X_{1}) ≤ ∑_{j=1}^{k} \binom{n − 1}{j}j^{k} \frac{(cj)^{j}}{n^{j}} ≤ ∑_{j=1}^{k} k^{k} \frac{c^{j}j^{j}}{j!} ≤ c^{k}k^{k},

which completes the proof of part (a).

(b) By (a),

Ee^{tD(X_{1})} = ∑_{k=0}^{∞} \frac{t^{k}}{k!} ED^{k}(X_{1}) ≤ ∑_{k=0}^{∞} \frac{t^{k}C_{d}^{k}k^{k}}{k!} ≤ ∑_{k=0}^{∞}(tC_{d}e)^{k} ≤ 2,

provided t ≤ 1/2eC_{d}. The second inequality follows by Chebyshev’s inequality.

(iii) Proximity graphs. The methods used for the sphere of influence graph can be applied with minor changes to other constructions that are of interest in computational geometry. We will discuss briefly what have been labeled proximity graphs by Devroye [4]. Given n points, x_{1}, …, x_{n}, one draws an edge between x_{i} and x_{j} if and only if a certain region S(x_{i}, x_{j}) contains x_{i}, x_{j} and no other sites. Typical examples are the relative neighbor graph (RNG) and the Gabriel graph (GG). In the first one, S(x_{i}, x_{j}) is a lens which is the intersection of two balls centered and x_{i} and x_{j}, respectively, having radius equal to |x_{i} − x_{j}|, while in GG S(x_{i}, x_{j}) is a ball centered at (x_{i} + x_{j})/2 with radius |x_{i} − x_{j}|/2. Our terminology follows Preparata and Shamos [12], which provides more information on these constructions as well as on their applications. We will mention here only that since S_{GG}(x_{i}, x_{j}) ⊂ S_{RNG}(x_{i}, x_{j}), RNG is a subgraph of GG, and thus e_{RNG} ≤ e_{GG} (and both are of order n). Here, and throughout the rest of this section, e with a corresponding subscript denotes the number of edges in a graph whose name is indicated in the subscript. Occasionally, when the argument applies in general, we will omit the subscript. It is known that RNG is a supergraph of the MST and GG is a subgraph of the DT, where MST and DT represent the minimum spanning tree and the Delaunay triangulation, respectively, of n points (although neither MST nor DT is a proximity graph in the sense described above). Let us recall that in DT, there is an edge between x_{i} and x_{j} if and only if there is a ball which has both of these two points on the surface and which contains no other points.

In order to bound the variance via the Efron – Stein inequality note that e − e_{i}^{∗} ≤ deg(X_{i}), and e_{i}^{∗} − e ≤ J_{i}, where

J_{i} = card{(j, k) : X_{i} ∈ S_{j,k}, X_{m} ∉ S_{j,k}; m ≠ i, j, k},

where for simplicity of notation we write S_{i,j} = S(X_{i}, X_{j}). Hence,

(e − e_{i}^{∗})^{2} ≤ deg^{2}(X_{i}) + J_{i}^{2}

and we need to show

E deg^{2}(X_{1}) ≤ C  and  EJ_{1}^{2} ≤ C.

Since deg_{RNG}(X_{1}) ≤ deg_{GG}(X_{1}), we will show that E deg_{GG}^{2}(X_{1}) ≤ C. (Note, that deg_{RNG} ≤ C, but this is not necessarily true for GG). By the same argument as for SIG, we need to bound P_{s,t}(I_{1,2} ∩ I_{1,3}), for t > s > 0. But, if |X_{1} − X_{2}| = s, |X_{1} − X_{3}| = t, and s < t then

P_{s,t}(I_{1,2} ∩ I_{1,3}) ≤ (1 − vol(B_{t/2}((X_{1} + X_{3})/2) ∩ [0, 1]^{d}))^{n−3} ≤ (1 − c_{d}(t/2)^{d})^{n−3} ,

and the bound on ED^{2}(X_{1}) follows by the same integration. To bound EJ_{1}^{2} let J_{j,k} denote the event {X_{1} ∈ S_{j,k}, X_{m} ∉ S_{j,k}; m ≠ 1, j, k} as well as its indicator. Then

\begin{aligned}EJ_{1}^{2} = ∑_{(j,k),(ℓ,m)} P(J_{j,k} ∩ J_{ℓ,m}) & = \binom{n − 1}{2}P(J_{2,3}) + 2\binom{n − 1}{2}(n − 3)P(J_{2,3} ∩ J_{2,4}) \\ & + \binom{n − 1}{2}\binom{n − 3}{2}P(J_{2,3} ∩ J_{4,5}), \end{aligned}

and we need to show that each of those terms is bounded. If P_{s}( · ) is the conditional probability given that |X_{2} − X_{3}| = s, then

P_{s}(J_{2,3}) = vol(S_{2,3})(1 − vol(S_{2,3} ∩ [0, 1]^{d}))^{n−3} ≤ Ks^{d}(1 − Ks^{d})^{n−3},

and integrating against the density of the distance between X_{2} and X_{3} we see that the first term is bounded. A proof of the second bound is similar; with obvious notation we have

\begin{aligned}P_{s,t}(J_{2,3} ∩ J_{2,4}) & = vol(S_{2,3} ∩ S_{2,4}) (1 − vol(S_{2,4} ∩ [0, 1]^{d}))^{n−4} \\ & ≤ Ks^{d} (1 − K(t^{d} + s^{d})/2)^{n−4} , \end{aligned}

if t > s. The computation for the third probability is essentially the same, except that X_{1} ∈ S_{2,3} ∩ S_{4,5} entails that |X_{2} − X_{4}| ≤ diam(S_{2,3}) + diam(S_{4,5}), and if |X_{2} − X_{3}| = s and |X_{4} − X_{5}| = t, then diam(S_{2,3}) + diam(S_{4,5}) ≤ K(s + t). Thus

\begin{aligned}P_{s,t}(J_{2,3} ∩ J_{4,5}) & = P_{s,t} (J_{2,3} ∩ J_{4,5})||X_{2} − X_{4}| ≤ K(s + t)) P_{s,t}(|X_{2} − X_{4}| ≤ K(s + t)) \\ & ≤ Ks^{d}(s^{d} + t^{d}) (1 − Kt^{d})^{n−5} , \end{aligned}

andthe last estimate follows.

As for the lower bound, the basic principle is the same as for the sphere of influence graph: we subdivide the unit cube into small cubes, and consider those cubes for which there is a boundary behavior that isolates the behavior inside the cube from the developments outside that cube and for which there is a fixed number of points near the center of the cube. A variability in the placements of those central points will cause variability in the number of edges within that cube, and since the average number of cubes for which that happens is of order n, and different cubes behave independently, superlinearity of the variance follows. For example, for GG, assuming d = 2 for simplicity, after subdividing the unit square into Q_{i}’s as before, consider the event A_{i} that the square Q_{i} contains exactly 5 points located as follows. Assuming Q_{i} = [a − h, a + h] × [b − h, b + h], let x^{0} be its center (a, b) and let y_{1}^{0}, …, y_{4}^{0} be the four points (a ± \frac{1}{2}h, b), (a, b ± \frac{1}{2}h); A_{i} then is the event that Q_{i} contains exactly five points x, y_{1}, …, y_{4} with |x − x^{0}| < εh and |y_{j} − y_{j}^{0}| < δh, where ε and δ are some fixed small numbers.

It is easily seen that if first ε and then δ are chosen small enough, then A_{i} implies the following, denoting the points outside Q_{i} by {z_{j}}:

(i) If a Gabriel sphere S(z_{j}, z_{k}) or S(z_{j}, y_{k}) contains x, then it also contains some y_{l} in its interior.

(ii) A Gabriel sphere S(z_{j}, x) always contains some y_{k}. (iii) A Gabriel sphere S(y_{j}, x) never contains any other point. (iv) A Gabriel sphere S(y_{j}, y_{k}) contains no other point except possibly x; moreover, if y_{j}

and y_{k} do not lie opposite each other, both S(y_{j}, y_{k}) and its complement intersect {x : |x − x^{0}| < εh}. It follows that conditioned on A_{i}, moving around the central point x may only affect

the edges between the y_{j}’s, and the number of such edges will vary and has a non-zero variance. Consequently, conditioning as before on everything except the location of the central point for those Q_{i}’s for which A_{i} occurs, we obtain a lower bound of order n on the variance of N_{GG}. For RNG the construction is similar.

It should be noted that this approach for a lower bound does not work for DT. In fact, the result is not true for DT. For example, if d = 2 and X_{i}’s are uniformly distributed on the unit square then the variance of the number of edges in DT is of order log n rather than n. This is perhaps a bit surprising, especially if one takes into account the fact that the total length of the edges in DT has variance of order n (see [1]). To see that variance of the number of edges in DT (or any other triangulation, for that matter) is of order log n one just notes that e_{DT} is linked to the number of extreme points of the convex hull of X_{i}’s by the formula e_{DT} = 3(n − 1) − card{ext(conv({X_{i}}))}, so that var(e_{DT}) is equal to the variance of the number of extreme points in the sample X_{1}, …, X_{n}. But the latter variance is of order log n if the X_{i}’s are i.i.d. uniform on the unit square [8]. This means that the behavior of DT is not really “local” which is perhaps a bit counterintuitive.

Acknowledgment. The first author would like to thank Rex Dwyer from the Department of Computer Science at North Carolina State University for several useful conversations.

References.

1. Avram, F. and Bertsimas, D. (1993) On central limit theorems in geometric probability, Ann. Appl. Probab. 3, 1033 – 1046.

2. Baldi, P. and Rinott, Y. (1989) On normal approximations of distributions in terms of dependency graphs, Ann. Probab. 17, 1646-1650.

3. Chalker, T. K., Godbole, A. P., Hitczenko, P., Radcliff, J. and Ruehr, O. G. (1997) On the size of a random sphere of influence graph, preprint.

4. Devroye, L. (1988) The expected size of some graphs in computational geometry, Computer Math. Appl. 15, 53 – 64.

5. Dwyer, R. A. (1995) The expected size of the sphere of influence graph, Comp. Geometry 5, 155 – 164.

6. Efron, B. and Stein, C. (1981) The jackknife estimate of variance, Ann. Statist. 9, 586 – 596.

7. Füredi, Z. (1995) The expected size of a random sphere of influence graph, Intuitive Geometry, Bolyai Mathematical Society, 6, 319 – 326.

8. Groeneboom, P. (1988) Limit theorems for convex hulls, Probab. Theory Rel. Fields 79, 327-368.

9. Janson, S. (1988) Normal convergence by higher semiinvariants with applications to sums of dependent random variables and random graphs, Ann. Probab. 16, 305-312.

10. Michael, T. S. and Quint, T. (1994) Sphere of influence graphs: a survey, Congressus Numerantium 105, 153–160.

11. Petrovskaya, M. and Leontovitch, A. (1982) The central limit theorem for a sequence of random variables with a slowly growing number of dependencies, Theory Probab. Appl. 27, 815-825.

12. Preparata, F. P. and Shamos, M. I. (1985) Computational Geometry. An Introduction. Springer.

13. Steele, J. M. (1997) Probability Theory and Combinatorial Optimization, NSF-CBMS Regional Research Conference Lecture Notes Series Vol. 69, Society for Industrial and Applied Mathematics, Philadelphia.

14. Steele, J. M. (1995) Variations on the monotone subsequence theme of Erdös and Szekeres, Discrete Probability and Algorithms, volume 72, D. Aldous, P. Diaconis, J. Spencer and J. M. Steele, eds. The IMA Volumes in Mathematics and Its Applications, Springer.

15. Toussaint, G. T. (1980) Pattern recognition and geometric complexity. Proceedings of the 5th International Conference on Pattern Recognition, Miami Beach, FL, 1324– 1347.

16. Yukich, J. E. (1998) Probability Theory of Classical Euclidean Optimization Problems, Lecture Notes Math., 1675, Springer.

P. Hitczenko  S. Janson
Department of Mathematics  Department of Mathematics
North Carolina State University  Uppsala University
Raleigh, NC 27695–8205, USA  S – 751 06 Uppsala, Sweden

e-mail: pawel@math.ncsu.edu             e-mail: svante@math.uu.se

J.E. Yukich Department of Mathematics Lehigh University Bethlehem, PA 18015

e-mail: jey0@lehigh.edu