La distribución más uniforme de puntos en la esfera es una tarea increíblemente importante en matemáticas, ciencias y sistemas informáticos, y la aplicación de una cuadrícula de Fibonacci a la superficie de una esfera usando la misma proyección es un método de aproximación extremadamente rápido y eficiente para resolverlo. Mostraré cómo, con cambios menores, se puede hacer aún mejor.

Hace algún tiempo, esta publicación apareció en la página principal de Hacker News. Su discusión se puede leer aquí .

Introduccion

El problema de la distribución uniforme de puntos en una esfera tiene una historia muy larga. Este es uno de los problemas mejor estudiados en la literatura matemática sobre geometría esférica. Es de importancia crítica en muchas áreas de las matemáticas, la física, la química, incluidos los métodos computacionales, la teoría de la aproximación, la teoría de la codificación, la cristalografía, la electrostática, los gráficos por computadora, la morfología de virus y muchos otros.

Desafortunadamente, con la excepción de algunos casos especiales (a saber, sólidos platónicos), es imposible distribuir perfectamente los puntos en una esfera. Además, la solución del problema depende en gran medida del criterio utilizado para evaluar la uniformidad. En la práctica, se utilizan muchos criterios , que incluyen:

Embalaje y revestimiento
Cascos convexos, células Voronoi y triángulos Delaunay.
Granos $s$ Energía del arroz
Cubature y calificadores

Es muy importante aclarar este aspecto: generalmente no existe una solución óptima única para este problema, porque una solución óptima basada en un criterio a menudo no es una distribución óptima de puntos para otros. Por ejemplo, también descubriremos que la optimización del empaque no necesariamente crea un casco convexo óptimo y viceversa.

En aras de la brevedad, en esta publicación consideraremos solo dos criterios: la distancia mínima de empaque y el casco convexo / malla Delaunay (volumen y área).

En la sección 1, mostramos cómo puede cambiar la cuadrícula canónica de Fibonacci para construir una distribución mejorada del empaque . En la Sección 2, mostramos cómo puede cambiar la rejilla canónica de Fibonacci para construir parámetros mejorados para cascos convexos (volumen y área de superficie).

Sección 1. Optimización de la distancia de embalaje.

A menudo, este problema se llama la tarea de Tamm en honor del botánico Tems, que buscaba una explicación de la estructura superficial de los granos de polen. El criterio de empaque requiere que maximicemos la distancia más pequeña entre vecinos para

$N$ puntos. Eso es

$d_N = \ min_ {i \ neq j} | x_i - x_j |$

Este valor disminuye con la velocidad.

$~ 1 / \ sqrt {N}$ , por lo tanto, será útil determinar la distancia normalizada, así como el límite asintótico de la distancia normalizada, como

$d ^ * _ N = \ sqrt {N} d_N, \ quad \ quad d ^ * = \ lim_ {N \ rightarrow \ infty} d ^ * _ N$

Rejilla de Fibonacci

Una solución muy elegante modela los nodos que se encuentran en la naturaleza, por ejemplo, la distribución de semillas en un cono de girasol o pino. Este fenómeno se llama filotaxis espiral. Coxeter demostró que tales estructuras tienen una conexión fundamental con la serie Fibonacci,

F_k = \ {1, 1, 2, 3, 5, 8, 13, ... \}

$F_k = \ {1, 1, 2, 3, 5, 8, 13, ... \}$ y la proporción áurea

$\ phi = (1+ \ sqrt {5}) / 2$ .

En la literatura, se encuentran dos definiciones similares del conjunto de puntos de una rejilla esférica de Fibonacci. La fuente se define estrictamente para

$N$ igual a uno de los miembros de la serie Fibonacci,

$F_m$ , y bien estudiado en teoría de números.

$t_i = \ left (\ frac {i} {F_m}, \ frac {i F_ {m-1}} {F_m} \ right) \ quad \ textrm {for} \; 0 \ leq i \ leq N-1$

La segunda definición generaliza la fórmula a una cantidad arbitraria

$N$ y se usa en cálculos con más frecuencia:

$t_i = \ left (\ frac {i} {N}, \ frac {i} {\ phi} \ right) \ quad \ textrm {for} \; 0 \ leq i \ leq N \ tag {1}$

donde

$\ phi = \ frac {1+ \ sqrt {5}} {2} = \ lim_ {n \ rightarrow \ infty} \ left (\ frac {F_ {n + 1}} {F_n} \ right)$

A continuación se muestra un ejemplo de las mismas cuadrículas de Fibonacci. Mediante la transformación, puede convertir estos conjuntos de puntos en espirales de Fibonacci que conocemos bien.

$(r, \ theta) = (\ sqrt {x_1}, 2 \ pi x_2)$

Del mismo modo, estos conjuntos de puntos se pueden transferir desde el cuadrado de la unidad

$[0, 1] ^ 2$ en una esfera usando una proyección isométrica cilíndrica:

$(x, y) \ rightarrow (\ theta, \ phi): \ quad \ left (\ cos ^ {- 1} (2x-1) - \ pi / 2, 2 \ pi y \ right)$

$(\ theta, \ phi) \ rightarrow (x, y, z): \ quad \ left (\ cos \ theta \ cos \ phi, \ cos \ theta \ sin \ phi, \ sin \ theta \ right)$

Se pueden encontrar muchas versiones diferentes del código Python para él en stackoverflow: distribuir puntos uniformemente en una esfera .

Incluso a pesar del hecho de que los conjuntos esféricos de Fibonacci no son globalmente la mejor distribución de muestras en una esfera (porque sus soluciones no coinciden con las soluciones para sólidos platónicos para

$n = $ 4,6,8,12,2$ ), tienen excelentes propiedades de muestreo y son muy fáciles de construir en comparación con otros esquemas de muestreo esféricos más complejos.

Dado que la transferencia desde el cuadrado de la unidad a la superficie de la esfera se lleva a cabo mediante una proyección con preservación del área, se puede esperar que si los puntos de partida se distribuyen uniformemente, también se distribuirán bastante bien en la superficie de la esfera. Sin embargo, esto no significa que la distribución sea demostrablemente óptima.

Esta transferencia sufre de dos problemas diferentes pero interrelacionados.

En primer lugar, esta superposición se realiza manteniendo el área, no la distancia. Dado que en nuestro caso, la condición es maximizar la distancia mínima por pares entre puntos, tales condiciones y relaciones no se cumplirán necesariamente después de la proyección.

El segundo problema es más difícil de resolver desde un punto de vista práctico: la superposición tiene dos puntos degenerados en cada polo. Considere dos puntos que están muy cerca del poste, pero que difieren en 180 grados de longitud. En un solo cuadrado (y en una proyección cilíndrica) corresponderán a dos puntos muy distantes entre sí, sin embargo, cuando se superponen en la superficie de una esfera, se pueden conectar mediante un arco muy pequeño que atraviesa el polo norte. Debido a este problema particular, muchas superposiciones en espiral no son lo suficientemente óptimas.

La hélice esférica de Fibonacci obtenida de la ecuación 1 da el valor

$d_N ^ *$ para todos

$N$ eso es

$d ^ * = 2$ .

Malla 1

Una versión más común (especialmente en sistemas informáticos) que crea un mejor valor

$d ^ * = 3.09$ tiene la forma:

$t_i = \ left (\ frac {i + 1/2} {N}, \ frac {i} {\ phi} \ right) \ quad \ textrm {for} \; 0 \ leq i \ leq N-1 \ tag {2}$

Coloca los puntos en los puntos medios de los intervalos (de acuerdo con la regla del punto medio en la fórmula cuadrática de Gauss), por lo tanto, para

$n = 100$ , los valores de la primera coordenada serán los siguientes:

$\ {\ frac {0.5} {100}, \ frac {1.5} {100}, \ frac {2.5} {100}, \ ldots, \ frac {97.5} {100}, \ frac {98.5} {100} , \ frac {99.5} {100} \}$

Rejilla 2.

La clave para mejorar aún más la Ecuación 2 es darse cuenta de que

$d ^ * _ N$ siempre corresponde a la distancia entre puntos

$t_0$ y

$t_3$ que están en los polos Es decir, para mejorar

$d_N$ los puntos cerca de los polos deben estar espaciados aún más.

Si definimos la siguiente distribución:

$t_i (\ varepsilon) = \ left (\ frac {i + 1/2 + \ varepsilon} {N + 2 \ varepsilon}, \ frac {i} {\ phi} \ right) \ quad \ textrm {for} \ ; 0 \ leq i \ leq N-1$

$d ^ * _ N$ - curvas para varios valores.

$\ varepsilon = 0$ (azul);

$\ varepsilon = \ frac {1} {2}$ (naranja);

$\ varepsilon = \ frac {3} {2}$ (verde); y

$\ varepsilon = \ frac {5} {2}$ (rojo) Puedes ver eso

$\ varepsilon = \ frac {5} {2}$ da resultados más cercanos a los resultados asintóticos. Es decir, con

$N> 20$ La siguiente expresión simple genera resultados significativamente mejores.

$d ^ * = 3.29$ en comparación con la rejilla esférica canónica de Fibonacci:

$t_i = \ left (\ frac {i + 3} {N + 5}, \ frac {i} {\ phi} \ right) \ quad \ textrm {for} \; 0 \ leq i \ leq N-1 \ tag {3}$

Es decir, con

$N = 100$ Los valores de la primera coordenada serán iguales a:

$\ {\ frac {3} {105}, \ frac {4} {105}, \ frac {5} {105}, \ ldots, \ frac {100} {105}, \ frac {101} {105} , \ frac {102} {105} \}$

Figura 1. Diferentes valores

$d_N ^ *$ a diferentes valores

$\ epsilon$ . Cuanto mayor sea el valor, más óptima será la configuración. Vemos eso

$\ epsilon \ simeq 2.5$ Proporciona una solución cercana a la óptima.

Malla 3.

Como se mencionó anteriormente, uno de los problemas más serios de la distribución uniforme de puntos en una esfera es que la óptima distribución depende críticamente de la función objetivo utilizada. Resulta que que cantidades locales como

$d_N ^ *$ a veces casi "no perdonan los errores": un solo punto en una posición insuficientemente óptima puede reducir catastróficamente la evaluación de toda la distribución de puntos.

En nuestro caso, independientemente de la magnitud.

$N$ valor

$D_N ^ *$ generalmente definido por los cuatro puntos más cercanos a cada uno de los polos, especialmente

$t_0$ y

$t_3$ . Sin embargo, también se sabe sobre esta cuadrícula que el polígono Voronoi más grande está en el polo. Entonces tratando de maximizar

$d_N$ Al dividir los puntos polares originales en una fila, en realidad aumentamos aún más el vacío en el poste. Por lo tanto, presentamos una alternativa a la cuadrícula 2, que generalmente es preferible porque no muestra un vacío tan grande cerca de los polos.

Es casi idéntico a la cuadrícula 2, pero tiene dos diferencias. Primero, ella usa

$\ varepsilon = 11/2$ a las

$1 \ leq i \ leq N-2$ . En segundo lugar, además de estos

$N-2$ El primer y el último punto están ubicados en cada uno de los polos.

Eso es:

$t_0 = (0,0); \; t_n = (1,0); \ quad t_i = \ left (\ frac {i + 6} {N + 11}, \ frac {i} {\ phi} \ right) \ quad \ textrm {for} \; 1 \ leq i \ leq N-2 \ tag {4}$

Una propiedad sorprendente de este método de construcción es que, a pesar de que su creación fue motivada por el deseo de minimizar los vacíos en los polos, en realidad tiene el mejor valor entre todos los métodos.

$d_N$ y

$d ^ *$ con

$d ^ * = 3.31$ !

Es decir, con

$N = 100$ Los valores de la primera coordenada serán los siguientes:

$\ {0; \; \ frac {7} {111}, \ frac {8} {111}, \ frac {9} {1111}, \ ldots, \ frac {102} {111}, \ frac {103} {111}, \ frac {104} {111}; \; 1 \}$

Figura 2. Diversas configuraciones de cuadrícula. La rejilla canónica de Fibonacci a la izquierda. Tenga en cuenta que a pesar de que la cuadrícula media

$d_N ^ *$ mejorado, en el poste tiene un vacío notable. La cuadrícula 3 no tiene vacío en el poste y tiene el mejor valor

$d_N ^ *$ .

Comparación

Para grandes valores

$N$ este valor

$d ^ *$ extremadamente comparable con otros métodos, por ejemplo, domos geodésicos, que se basan en proyecciones trianguladas de las caras de los sólidos platónicos en la superficie de una esfera. No es sorprendente que las cúpulas geodésicas de la más alta calidad se construyan sobre la base del icosaedro o el dodecaedro.

Domos geodésicos basados en icosaedro a varios valores

$N$ .

$\ begin {array} {| c | cccccccccc |} \ hline N y 12 y 42 y 92 y 162 y 252 y 362 y 492 y 642 y 812 y 1002 \\ \ hline d ^ * y 3.64 y 3.54 y 3.34 y 3.22 & 3.15 & 3.09 & 3.06 & 3.03 & 3.00 & 2.99 \\ \ hline \ end {array}$

Domos geodésicos basados en dodecaedros para varios valores

$N$ .

$\ begin {array} {| c | ccccccc |} \ hline N y 20 y 32 y 122 y 272 y 482 y 752 y 1082 \\ \ hline d ^ * y 3.19 y 3.63 y 3.16 y 2.99 y 2.90 y 2.84 y 2.81 \\ \ hline \ end {array}$

Además, un icosaedro truncado que corresponde a la forma del fullereno.

$C_ {60}$ solo tiene

$d ^ * = 3.125$ .

Es decir, con

$N> 100$ La malla basada en la ecuación 3 es mejor que cualquier poliedro geodésico.

Según los datos de la primera fuente en la lista de referencias a continuación, algunos de los métodos modernos, que generalmente son complejos y requieren una programación recursiva y / o dinámica, tienen los siguientes indicadores.

$\ begin {array} {| lr |} \ hline \ text {Lattice 1} & 3.09 \\ \ hline \ text {Max Determinant} & 3.19 \\ \ hline \ text {Lattice 2} & 3.28 \\ \ hline \ text {Lattice 3} & 3.31 \\ \ hline \ text {Zonal Equal Area} & 3.32 \\ \ hline \ text {Coulomb} & 3.37 \\ \ hline \ text {Log Energy} & 3.37 \\ \ hline \ end { matriz}$

Conclusión de la Sección 1

La cuadrícula 3, creada por la ecuación 3, es una modificación de la cuadrícula canónica de Fibonacci, que proporciona un empaquetado mucho mejor para la distribución de puntos. Eso es

$t_0 = (0,0); \; \; t_i = \ left (\ frac {i + 6} {N + 11}, \ frac {i} {\ phi} \ right); \; \; t_ {N-1} = (0,1); \ quad \ textrm {para} \; 1 \ leq i \ leq N-2$

Sección 2. Optimización del casco convexo (malla Delaunay)

En la sección anterior, optimizamos la distribución por

$d ^ * _ N$ Sin embargo, estas modificaciones empeoran otros indicadores, por ejemplo, el volumen de un casco convexo (malla de Delaunay). Esta sección describe cómo distribuir uniformemente los puntos en una esfera de manera que se optimice (maximice) un indicador más global como el volumen de un casco convexo.

Denotamos

$C_N$ como un casco convexo

$N$ puntos

$\ epsilon_N = N \ left (\ frac {4 \ pi} {3} \; - \ textrm {Vol} (C_N) \ right)$

factor de normalización incluido

$N$ , porque la discrepancia absoluta disminuye con la velocidad

$~ 1 / N$ .

Comportamiento

$\ epsilon_N$ en varios

$N$ se puede ver en la Figura 3 (línea azul).

Para reducir la falta de coincidencia de los volúmenes, debe tenerse en cuenta que a pesar del uso de

$\ phi$ , de la lógica de la sección dorada en

$N \ rightarrow \ infty$ no necesariamente se deduce que es el mejor valor para la final

$N$ . Hablando científicamente, podemos decir que debemos tener en cuenta la influencia de la corrección de las extremidades.

Resumamos la ecuación 1 de la siguiente manera:

$t_i = \ left (\ frac {i + 1/2} {N}, \ frac {i} {g (N)} \ right) \ quad \ textrm {for} \; 0 \ leq i \ leq N-1 \ tag {4}$

donde definimos

$g (n)$ como

$g (n) = \ begin {cases} 3- \ phi, & \ text {if $ k $ es par} \\ \ phi, & \ text {if $ k $ es impar} \ end {cases} \ tag {5}$

donde

$k = \ left \ lfloor \ textrm {log} _ {\ phi} (\ frac {n} {1.5}) \ right \ rfloor = \ left \ lfloor \ frac {\ ln (n / 1.5)} {\ ln \ phi} \ right \ rfloor$

donde

$\ lfloor x \ rfloor$ - la función de redondear al entero más cercano hacia abajo.

La Figura 3 muestra la cantidad de desajuste de volumen optimizado para la mitad de los valores.

$N$ .

La razón de esto es un hecho poco conocido: todos los números

$x$ Satisfacer la transformación especial de Mobius, a partir de la irracionalidad, son equivalentes

$\ phi$ .

$x = \ frac {a \ phi + b} {c \ phi + d}, \ quad \ textrm {para todos los enteros} \; \; a, b, c, d \; \ textrm {tal que} | ad-bc | = 1$

Por lo tanto, la razón que

$\ phi$ y

$3- \ phi$ encajan tan bien, es que

$\ frac {1} {\ phi} = \ frac {\ phi + 1} {2 \ phi + 1}, \ quad \ quad \ frac {1} {3- \ phi} = \ frac {2 \ phi + 1} {1 \ phi + 1}$

Figura 3. La falta de coincidencia entre el volumen del casco convexo de puntos y el volumen de la esfera de la unidad. Tenga en cuenta que cuanto más pequeño sea, mejor. La figura muestra que el modelo híbrido (línea naranja) basado en

$\ phi$ y

$3- \ phi$ , proporciona una mejor distribución de puntos que la cuadrícula canónica de Fibonacci (línea azul).

Para la mitad restante, primero definimos una serie auxiliar

$A_N$ siendo una variación de la serie de Fibonacci

$A_1 = 1, \; A_2 = 4; \; A_ {n + 2} = A_ {n + 1} + A_n \; \ textrm {para} n = 1,2,3, ...$

Eso es

$A_N = 1,4,5,9,14,23,37,60,97,157,254,411, ...$

Todas las fracciones de esta serie tienen fracciones continuas elegantes, y en el límite convergen para

$\ phi$ . Por ejemplo

$t _5 / t_4 = 1+ \ cfrac {1} {1+ \ cfrac {1} {1+ \ cfrac {1} {1+ \ cfrac {1} {4}}}}$

Ahora podemos generalizar completamente

$g (n)$ como sigue:

$g (N) = \ begin {cases} 3- \ phi, & \ text {si $ k $ es par} \\ A_ {j + 1} / A_j, y \ text {si $ k $ es impar, donde $ j = (k + 7) / 2 $} \ end {cases} \ tag {6}$

La siguiente tabla muestra los valores

$g (N)$ para varios

$N$ .

$\ begin {array} {| c | c | c | c | c | c | c | c | c |} \ hline N y 4-6 y 7-10 y 11-16 y 17-26 y 27-43 y 44- 70 y 71-114 y 115-184 y 185-300 \\ \ hline g (n) y 3- \ phi & \ frac {23} {14} y 3- \ phi & \ frac {37} {23} y 3- \ phi & \ frac {60} {37} & 3- \ phi & \ frac {97} {60} y 3- \ phi \\ \ hline \ end {array}$

La Figura 4 muestra que con respecto al volumen del casco convexo, esta nueva distribución es mejor que la cuadrícula canónica para todos los valores.

$n$

Figura 4. La falta de coincidencia entre el volumen del casco convexo y el volumen de la esfera de la unidad. Cuanto menor sea el valor, mejor. Esto nos dice que el nuevo método propuesto (línea verde) proporciona constantemente una mejor distribución que la cuadrícula canónica de Fibonacci (línea azul).

Figura 5. Comparación visual de la malla canónica (izquierda) con la nueva malla modificada (derecha) con n = 35 yn = 150. Visualmente, las diferencias son casi imperceptibles. Sin embargo, en condiciones que requieren la máxima eficiencia, la versión modificada (a la derecha) proporciona una mejora pequeña, pero cuantificable, tanto en volumen como en área de superficie del casco convexo.

Curiosamente, esta distribución también es insignificante, pero reduce constantemente el desajuste entre el área de superficie del casco convexo y el área de superficie de una sola esfera. Esto se muestra en la Figura 6.

Figura 5. Desajuste normalizado de áreas entre el área de superficie de un casco convexo (malla de Delaunay) y el área de superficie de una sola esfera. Cuanto menor sea el valor, mejor. Esto muestra que la nueva modificación propuesta (puntos verdes) demuestra una disminución pequeña pero constante en la diferencia en las áreas de superficie en comparación con la cuadrícula canónica de Fibonacci (puntos azules)

Conclusión de la Sección 2

La cuadrícula correspondiente a la Ecuación 6 es una modificación de la cuadrícula de Fibonacci canónica, creando una distribución significativamente mejor de los puntos en función del volumen y el área de superficie del casco convexo (cuadrícula de Delaunay).

Fuentes

Distribución uniforme de puntos en una esfera.

Introduccion

Sección 1. Optimización de la distancia de embalaje.

Sección 2. Optimización del casco convexo (malla Delaunay)

More articles: