Considere la posibilidad de un gran conjunto de puntos con coordenadas que están distribuidos de manera uniforme dentro de una unidad de longitud del segmento. Considere la posibilidad de un diagrama de Voronoi construido sobre estos puntos. Si tenemos en cuenta que no sólo infinita de las células, lo que sería (si la hubiere), el típico (más frecuente) número de aristas (que es, vecinos) para las células? Hay un límite para este número al número de puntos que se extiende hacia el infinito? Tiene nada en común con kissing number? Si es así, haces que generalizar a dimensiones superiores, es decir, 6 de 2D, 13 de 3D etc?
Respuestas
¿Demasiados anuncios?
theog
Puntos
585
No tengo acceso al libro que @lhf que se hace referencia, pero aquí es un buen topológico argumento para el esperado número de aristas de Voronoi de células en $2$D. por Desgracia, no generalizar para más de dos dimensiones.
Considerar el doble de los diagrama de Voronoi, que es el de la triangulación de Delaunay de los puntos dados. Este es un plano de grafo conexo, por lo que su característica de Euler es $\chi = 2$. La característica de Euler es también dado por $\chi = V - E + F$, donde $V$, $E$, y $F$ es el número de vértices, aristas y caras en las triangulaciones de Delaunay, respectivamente. Ahora cada cara tiene $3$ bordes, mientras que todos los no-límite de los bordes adyacentes de a $2$ caras. Bajo condiciones razonables*, la proporción de aristas de contorno tiende a cero, así que vamos a ignorarlos. Esto significa que $3F \approx 2E$, y conectando de a $V - E + F = 2$ da $V \approx \frac13E + 2$, "$\approx$ " me refiero a la relación tiende a $1$$V \to \infty$. Así que hay cerca de tres veces más en los bordes de los vértices, y desde cada borde es incidente en $2$ vértices, el promedio de grado de los vértices de los enfoques $6$. Como el grado de un vértice de la triangulación de Delaunay es, precisamente, el número de aristas de la correspondiente celda de Voronoi, esto está de acuerdo con su intuición para la $2$D caso. (Aunque, estrictamente hablando, el esperado número de aristas no es el mismo como el más frecuente el número de aristas).
En tres dimensiones, la característica de Euler es todavía $2$, pero es que ahora se le da por $V - E + F - C$ donde $C$ es el número de tetraédrica células en la triangulación. Un argumento similar como la de arriba da $4C \approx 2F$, pero no tenemos control sobre las $E$. De hecho, hay triangulaciones en el mismo conjunto de puntos con el mismo límite (convex hull), pero que tienen diferentes números de los bordes. En el $2$D caso, cada una de estas triangulación tenía exactamente el mismo número de aristas! Así, en $3$D uno tendrá que pensar acerca de la geometría del diagrama de Voronoi y/o triangulaciones de Delaunay, y no puede obtener un resultado puramente a través de su topología.
* Creo que es suficiente para que los puntos que se pueden extraer de una distribución uniforme en un sentido estrictamente convexa de la zona, pero no sé los detalles.
Creo que el libro Espacial tessellations : conceptos y aplicaciones de los diagramas de Voronoipor OKABE, BOTAS,y SUGIHARA explica esto.
