Esfera delimitadora

Dichas esferas son útiles para la agrupación , donde se clasifican juntos grupos de puntos de datos similares.

En el análisis estadístico, la dispersión de los puntos de datos dentro de una esfera puede atribuirse a errores de medición o a procesos naturales (generalmente térmicos), en cuyo caso el grupo representa una perturbación de un punto ideal. En ciertas circunstancias, este punto ideal puede utilizarse como sustituto de los puntos del grupo, lo que resulta ventajoso para reducir el tiempo de cálculo.

En la investigación operativa, la agrupación de valores en un punto ideal también puede utilizarse para reducir el número de entradas y obtener valores aproximados para problemas NP-difíciles en un tiempo razonable. El punto elegido no suele ser el centro de la esfera, ya que este puede verse afectado por valores atípicos, sino que se calcula una posición promedio, como un punto de mínimos cuadrados, para representar el grupo.

Nimrod Megiddo estudió extensamente el problema del centro único y publicó sobre él al menos cinco veces en la década de 1980. ^{[ 2 ]} En 1983, propuso un algoritmo de " poda y búsqueda " que encuentra la esfera delimitadora óptima y se ejecuta en tiempo lineal si la dimensión se fija como una constante. Cuando la dimensión${\displaystyle d}$Se tiene en cuenta la complejidad del tiempo de ejecución.${\displaystyle O(2^{O(d^{2})}n)}$, ^{[ 3 ] [ 4 ]} lo cual es poco práctico para aplicaciones de alta dimensión.

En 1991, Emo Welzl propuso un algoritmo aleatorio mucho más simple , generalizando un algoritmo de programación lineal aleatorio de Raimund Seidel . El tiempo de ejecución esperado del algoritmo de Welzl es${\displaystyle O((d+1)(d+1)!\ n)}$, que nuevamente se reduce a${\displaystyle O(n)}$para cualquier dimensión fija${\displaystyle d}$El artículo proporciona resultados experimentales que demuestran su practicidad en dimensiones superiores. ^{[ 5 ]} Un algoritmo determinista más reciente de Timothy Chan se ejecuta en${\displaystyle O(d^{\left({\frac {1}{2}}+o(1)\right)d}n)}$, reduciendo nuevamente a${\displaystyle O(n)}$tiempo con dimensión fija, con una dependencia menor, pero aún exponencial, de la dimensión. ^{[ 4 ]}

La biblioteca de algoritmos de geometría computacional de código abierto (CGAL) contiene una implementación del algoritmo de Welzl. ^{[ 6 ]}

La esfera más pequeña que encierra un conjunto finito de puntos también se puede calcular utilizando optimización convexa , específicamente programación de cono de segundo orden (SOCP). ^{[ 7 ]} Este enfoque formula el problema como la minimización del radio de una esfera sujeta a restricciones de segundo orden (cuadráticas) que requieren que cada punto se encuentre dentro o sobre la esfera. Explícitamente, el problema de optimización es:

minimizar: r

sujeto a: || x _i − c ||₂ ≤ r , para todo i

donde el centro c y el radio r son las variables de optimización, y x _i son los puntos de entrada. ^{[ 7 ]}

Esta formulación define un problema de optimización convexa que puede resolverse eficientemente utilizando métodos modernos de punto interior y solucionadores SOCP. Si bien este enfoque proporciona una formulación matemática exacta, la solución se calcula típicamente con alta precisión numérica en lugar de precisión de máquina exacta. Por lo tanto, ofrece una alternativa práctica a los algoritmos geométricos, especialmente en dimensiones superiores o al integrarse con otros métodos basados ​​en optimización. ^{[ 7 ]}

Esta formulación convexa se analiza en fuentes como el libro de optimización convexa de Boyd y Vandenberghe, y cuenta con amplio soporte en software de optimización convexa como CVX, CVXPY y MOSEK . ^{[ 7 ]}

En 1990, Jack Ritter propuso un algoritmo sencillo para encontrar una esfera delimitadora no mínima. ^{[ 8 ]} Se utiliza ampliamente en diversas aplicaciones por su simplicidad. El algoritmo funciona de la siguiente manera:

1. Elige un punto${\displaystyle x}$de${\displaystyle P}$buscar un punto${\displaystyle y}$en${\displaystyle P}$, que tiene la mayor distancia de${\displaystyle x}$;
2. Buscar un punto${\displaystyle z}$en${\displaystyle P}$, que tiene la mayor distancia de${\displaystyle y}$. Prepara una bola inicial${\displaystyle B}$, con su centro como punto medio de${\displaystyle y}$y${\displaystyle z}$, el radio como la mitad de la distancia entre${\displaystyle y}$y${\displaystyle z}$;
3. Si todos los puntos en${\displaystyle P}$están dentro de la pelota${\displaystyle B}$, entonces obtenemos una esfera delimitadora. De lo contrario, sea${\displaystyle p}$ser un punto fuera de la pelota, construye una nueva pelota que cubre ambos puntos${\displaystyle p}$y la bola anterior. Repita este paso hasta que se hayan cubierto todos los puntos.

El algoritmo de Ritter se ejecuta en tiempo${\displaystyle O(nd)}$en entradas que consisten en${\displaystyle n}$puntos en${\displaystyle d}$espacio de -dimensiones, lo que lo hace muy eficiente. Sin embargo, solo proporciona un resultado aproximado que suele ser entre un 5 % y un 20 % mayor que el óptimo. ^{[ 8 ]}

Bădoiu et al. presentaron un${\displaystyle 1+\varepsilon }$aproximación al problema de la esfera delimitadora, ^{[ 9 ]} donde una${\displaystyle 1+\varepsilon }$La aproximación significa que la esfera construida tiene un radio como máximo${\displaystyle (1+\varepsilon)r}$, dónde${\displaystyle r}$es el radio más pequeño posible de una esfera delimitadora.

Un coreset es un subconjunto pequeño, que${\displaystyle 1+\varepsilon }$La expansión de la solución en el subconjunto constituye una esfera delimitadora del conjunto completo. El conjunto central se construye incrementalmente añadiendo el punto más alejado al conjunto en cada iteración.

Kumar et al. mejoraron este algoritmo de aproximación ^{[ 10 ]} para que se ejecute en tiempo${\displaystyle O({\frac {nd}{\epsilon }}+{\frac {1}{\epsilon ^{4.5}}}\log {\frac {1}{\epsilon }})}$.

Fischer et al. (2003) propusieron un solucionador exacto, aunque el algoritmo no tiene un tiempo de ejecución polinomial en el peor de los casos. ^{[ 11 ]} El algoritmo es puramente combinatorio e implementa un esquema de pivoteo similar al método simplex para programación lineal , utilizado anteriormente en algunas heurísticas. Comienza con una esfera grande que cubre todos los puntos y la reduce gradualmente hasta que no se puede reducir más. El algoritmo presenta reglas de terminación correctas en casos de degeneraciones, pasadas por alto por autores anteriores; y un manejo eficiente de soluciones parciales, lo que produce una importante aceleración. Los autores verificaron que el algoritmo es eficiente en la práctica en dimensiones bajas y moderadamente bajas (hasta 10 000) y afirman que no presenta problemas de estabilidad numérica en sus operaciones de punto flotante. ^{[ 11 ]} Una implementación en C++ del algoritmo está disponible como proyecto de código abierto. ^{[ 12 ]}

Larsson (2008) propuso el método de "esfera óptima de puntos extremos" con velocidad controlable para la aproximación de precisión para resolver el problema de la esfera delimitadora. Este método funciona tomando un conjunto de${\displaystyle s}$vectores de dirección y proyectar todos los puntos sobre cada vector en${\displaystyle s}$;${\displaystyle s}$sirve como una variable de compromiso velocidad-precisión. Se aplica un solucionador exacto a la${\displaystyle 2s}$puntos extremos de estas proyecciones. El algoritmo luego itera sobre los puntos restantes, si los hay, expandiendo la esfera si es necesario. Para grandes${\displaystyle n}$Este método es órdenes de magnitud más rápido que los métodos exactos, a la vez que proporciona resultados comparables. Tiene un tiempo de caso máximo de${\displaystyle O(sn)}$. ^{[ 1 ]}