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.

Improve this question
$\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$
    – Ori Gurel-Gurevich
    Commented Jul 4, 2012 at 20:54

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @Benoît Kloeckner thank you very much ! so probably this number mainly depends on $k$. Is the dependence known ? $\endgroup$
    – Alexander Chervov
    Commented 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$
    – Benoît Kloeckner
    Commented 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

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .