6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jul 4, 2012 at 20:54

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @Benoît Kloeckner thank you very much ! so probably this number mainly depends on $k$. Is the dependence known ? $\endgroup$ Jul 4, 2012 at 13:25
  • $\begingroup$ 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. $\endgroup$ Jul 4, 2012 at 13:53
4
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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