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.