¿Número de celdas de Voronoi vecinas para un conjunto aleatorio de puntos en S^k o cubo [-1, 1]^k?

Question

Considere $S^k \subset R^{k+1} $ . Muestra $N$ puntos mediante una distribución, digamos, uniforme. (Ejemplo k=120, N=2^24, es decir N>>k ).

Considere Célula de Voronoi alrededor de cada punto.

¿Cuántos vecinos tiene una célula? Los vecinos son las celdas que tienen una intersección no vacía. "Cuántos" significa la media de la distribución. (Es evidente que es menor que N, ¿pero cuál es su comportamiento? ¿N/C, sqrt(N) o qué?)

En realidad no me interesa más la esfera sino el cubo: tomemos la unidad cubo $[-1, 1]^k$ . Y tomar al azar algún número $N$ de sus vértices. Las mismas preguntas.

---

Motivación:

Como intenté explicar en este MO búsqueda estos problemas están relacionados con la descodificación de la señal de ruido. Esta pregunta se puede traducir en este lenguaje de la siguiente manera - si hay oportunidad de hacer algún "preprocesamiento" de tal manera que reduciría significativamente la complejidad de decodificación. Es decir, si la respuesta es mucho menor que N, entonces sí; de lo contrario, no.

Answer 1

En $k=2$ se puede utilizar la combinatoria para evitar cualquier relación con la probabilidad. A partir de la fórmula de Euler, se obtiene que el grado medio de un grafo con $N$ vértices en $S^2$ es $6-\frac{12}N$ (véase, por ejemplo Pruebas del libro sección sobre la fórmula de Euler).

Aplicando esto al gráfico de vecinos de tu teselación, obtienes que el número medio de vecinos de una celda está acotado por $6$ independientemente de $N$ .

Para ello hay que descartar las celdas que se tocan sólo por una esquina (si no, el gráfico no tiene por qué ser plano), pero supongo que esto sólo ocurre con probabilidad nula.

Answer 2

Esto fue estudiado por Miles en los años setenta. Una buena referencia es el libro de Schneider y Weil. Los resultados pertinentes se encuentran en sección 10.2