viernes, 23 de marzo de 2012

Distribuyendo puntos en la esfera

Hoy voy a hablar de un problema abierto que conozco desde que un profesor mío que trabajaba sobre él me lo enseñó hace dos años, que me parece sencillo de comprender y no por ello menos interesante: se trata del problema número 7 de la lista de Smale.



El problema consiste en encontrar una forma de colocar $N$ puntos sobre la esfera $\mathbb{S}^2 = \{ (x,y,z) \in \mathbb{R}^3\ :\ x^2+y^2+z^2=1\}$ de manera que estén "bien distribuídos" en el siguiente sentido: podemos imaginar los puntos sobre la esfera como partículas cargadas que se repelen las unas a las otras según la ley de Coulomb. Lo que se pretende es que esta fuerza de repulsión sea mínima, de modo que los puntos sobre la esfera estén en "equilibrio", y para eso es necesario que estén bien repartidos. Si dos de los puntos están demasiado juntos, entonces la repulsión total será demasiado alta y no alcanzaremos el mínimo.

Lo que hacemos para medir la buena distribución de los puntos es usar una función. Dados $N$ puntos $x_1, x_2, ..., x_N \in \mathbb{S}^2$, se define la función de energía

$\prod_{1 \leq i < j \leq N}||x_i-x_j||$

dada por el producto de las distancias entre todos los puntos distintos. Nos interesa maximizar esta función. Si dos puntos $x_i$ y $x_j$ estuvieran muy juntos, $||x_i - x_j||$ sería un número muy pequeño y haría que el valor del producto cayese mucho. Pero maximizar esta función es equivalente a minimizar la función

$E(x_1, x_2, ..., x_N) = \sum_{1 \leq i < j \leq N} \log {1 \over {||x_i - x_j||}}$

que es la función sobre la cual estableceremos el problema del que habla Smale.

Problema. Escribir un algoritmo cuya entrada sea un número natural $N$ y cuya salida sean $N$ puntos $x_1, x_2, ..., x_N \in \mathbb{S}^2$ de forma que minimicen la función $E$ que acabamos de definir.

Es decir, lo que se nos pide es dar la manera explícita de colocar esos $N$ puntos para minimizar la función $E$. Lo primero que debemos preguntarnos es: ¿existen dichos puntos? O dicho de otro modo, ¿la función $E$ alcanza el mínimo global? Existen funciones continuas que no alcanzan el máximo ni el mínimo. Por ejemplo, la función $f(x) = x$ definida en el intervalo $(0,1)$ no alcanza su máximo. Un candidato sería $x = 1$, pero dicho punto no pertenece al intervalo de definición de $f$. Igual pasa si definimos $f$ en todo $\mathbb{R}$, que no alcanza máximo ni mínimo global.

Sin embargo nuestra función $E$ es mejor: podemos ver $E$ como una función

$E: \mathbb{S}^2 \times \mathbb{S}^2 \times ...^{N)} \times \mathbb{S}^2 \longrightarrow \mathbb{R}$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (x_1, x_2, ..., x_N) \longmapsto \sum_{1 \leq i < j \leq N} \log {1 \over {||x_i - x_j||}}$

que es continua salvo en los puntos en los que algún $x_i$ es igual a algún $x_j$ y se anula un denominador. Es decir, $E$ es continua salvo en el conjunto

$V = \{(x_1, ... x_N) \in \prod_{i=1}^N \mathbb{S}^2\ :\ \exists i, j$ tales que $x_i = x_j\}$

así que si ahora consideramos un entorno abierto pequeño $U$ de $V$ y cogemos unas tijeras, podemos podar los picos del grafo de $E$ de modo que $\prod_{i=1}^N \mathbb{S}^2$ era compacto y $\prod_{i=1}^N \mathbb{S}^2 \setminus U$ sigue siendo un compacto, sólo que ahora $E$ definida en $\prod_{i=1}^N \mathbb{S}^2 \setminus U$ es continua, y el teorema de Weierstrass nos asegura que una función continua definida en un subconjunto compacto de $\mathbb{R}^n$ alcanza su máximo y su mínimo. Por tanto hemos probado que los puntos que minimizan la función $E$ existen, que se llaman Juanito, Pedrito o Pablito y se les puede tocar.

De hecho para los casos $N = 4, 6, 8, 12$ y $20$ los puntos solución vienen dados por los vértices de los sólidos platónicos, respectivamente, el tetraedro, el octaedro, el cubo, el icosaedro y el dodecaedro. En estos casos los puntos son equidistantes: la distancia entre cada par de ellos es la misma. Esto podría darnos la idea de que, quizás, los puntos solución para $N$ cualquiera también deben ser equidistantes, pero esto no es posible. En general no se pueden colocar $N$ puntos equidistantes sobre la esfera $\mathbb{S}^2$ porque, interpretándolos como vértices de un poliedro, esto nos daría la posibilidad de construir poliedros regulares de $N$ vértices, y usando la característica de Euler es fácil probar que los únicos poliedros regulares posibles son los cinco sólidos platónicos. Esto significa que los puntos que queremos colocar tienen que estar "bien repartidos", pero no "perfectamente repartidos" porque hacer esto es imposible.

Las personas que han trabajado en este problema han ido proponiendo distintas maneras de colocar los puntos. Una de ellas es la distribución en espiral, que consiste en colocar los puntos alrededor de la esfera, como enrollando un largo collar de perlas, en una espiral que abraza toda la esfera.

Esta distribución es una primera aproximación, ya que los resultados que se obtienen son aceptables, pero no es la solución al problema. Otra idea que ha surgido es la de relacionar este problema con un problema de teselación de la esfera. El plano $\mathbb{R}^2$ se puede teselar usando sólo hexágonos regulares, pero este no es el caso de la esfera. Para teselar la esfera con hexágonos podemos añadirle, por ejemplo, un puñado de pentágonos.

Por medio de aproximaciones numéricas se ha observado que la configuración óptima del diagrama de Voronoi sobre la esfera para $N$ puntos (un problema íntimamente relacionado) cuando $N$ es grande consiste en hexágonos y exactamente $12$ pentágonos. Se sigue de la característica de Euler que cualquier teselación de la esfera que tenga únicamente hexágonos y pentágonos debe tener, exactamente, 12 pentágonos. El primer ejemplo de una teselación de estas características es un balón de fútbol corriente


Aunque no parecía en principio que el diagrama de Voronoi de los puntos que resuelven nuestro problema debiera tener una configuración como esta, podría ser una pista para la manera en la que debemos actuar, ya que estas configuraciones han dado muy buenos resultados en nuestro problema e, intuitivamente, parecen estar acorde con aquello que decíamos de que los puntos deben estar "bien distribuidos" pero no "perfectamente distribuídos", que encaja con que la mayoría de los polígonos que teselan la esfera son hexágonos, excepto 12 pentágonos que rompen un poco la simetría.

Por último, cabe mencionar que la resolución de este problema tiene multitud de aplicaciones prácticas en campos como la biología, la química, o la tecnología. Por ejemplo, en el análisis de los datos recogidos por un satélite sobre la superficie de la Tierra, en ocasiones nos interesa aproximar algunas integrales, y para aproximarlas bien necesitamos una buena distribución de $N$ puntos sobre la esfera terrestre en el sentido de este problema.

Añado también un vídeo de unos experimentos que estuve haciendo yo sobre este problema en Matlab. En el vídeo se ve cómo una serie de puntos colocados inicialmente en forma de espiral se van acomodando, moviéndose hacia la solución mínima.




1 comentario:

  1. y si construyeras una gran esfera con esferas pequeñas, una esfera de esferas, eso calculando la superficie de la esfera principal y de las pequeñas esferas. el punto de apoyo de estas esferitas daria puntos equidistantes entre unas y otras!! encontre la pagina buscando como hacer un dado de 100 lados y tiene q ser posible... jajajajajj!!

    ResponderEliminar