# Number of neigbour Voronoi cells for a random set of points on S^k or cube [-1, 1]^k?

Consider $S^k \subset R^{k+1}$. Sample $N$ points by say uniform distribution. (Example k=120, N=2^24, i.e. N>>k ).

Consider Voronoi cell around each point.

How many neighbours would a cell have ? I mean neigbours are the cells which have non empty intersection. "How many" means average over distribution. (Clearly it is less than N, but what is it behaviour ? N/C, sqrt(N) or what ?)

Actually I more interested not about the sphere but about the cube: take unit cube $[-1, 1]^k$. And take randomly some number $N$ of its vertexes. The same questions.

Motivatation:

As I tried to explain in this MO quest these problems are related to decoding noise signal. This question can be translated in this language as follows - if there chance to do some "preprocessing" such that it would significantly reduce decoding complexity. I mean in the answer is much smaller than N, then yes, otherwise, not.

-
In closely related Poisson-Voronoi tessellation, the degree grows exponentially with the dimension (I believe it is roughly $2^k$ up to lower order multiplicative terms, but I can't find a reference now). So the relevant condition seems to be whether $N$ is bigger then this. For your example parameters, I would expect most pairs of points to be adjacent. – Ori Gurel-Gurevich Jul 4 '12 at 20:54

When $k=2$, you can use combinatorics to avoid any relation with probability. From Euler formula, one gets that the mean degree of a graph with $N$ vertices on $S^2$ is $6-\frac{12}N$ (see e.g. Proofs from the book, section on Euler formula).

Applying this to the neighbors graph of your tesselation, you get that the average number of neighbors of a cell is bounded by $6$ independently of $N$.

For this you have to rule out cells that touch by a corner only (otherwise the graph need not be planar), but I guess this only happen with null probability.

-
@Benoît Kloeckner thank you very much ! so probably this number mainly depends on $k$. Is the dependence known ? – Alexander Chervov Jul 4 '12 at 13:25
I don't know more than I wrote. The argument above does not extend to higher dimensions as they are, I do not know if there are any restriction on the neighbors graph of a Voronoi diagram in higher dimension. – Benoît Kloeckner Jul 4 '12 at 13:53

This was studied by Miles in the seventies. A good reference is Schneider and Weil's book. The relevant results are in section 10.2

-
@Igor thank you very much ! – Alexander Chervov Jul 5 '12 at 6:15