MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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.

share|cite|improve this question
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.

share|cite|improve this answer
@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

share|cite|improve this answer
@Igor thank you very much ! – Alexander Chervov Jul 5 '12 at 6:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.