Esfera delimitadora

Esfera que contiene un conjunto de objetos

Algunos ejemplos del círculo delimitador más pequeño , el caso de la esfera delimitadora en 2 dimensiones.

En matemáticas , dado un conjunto no vacío de objetos de extensión finita en un espacio de dimensión 1 , por ejemplo un conjunto de puntos, una esfera delimitadora , una esfera envolvente o una bola envolvente , ese conjunto es una esfera sólida de dimensión 1 que contiene todos estos objetos. ${\displaystyle d}$ ${\displaystyle d}$

Una esfera delimitadora, que se utiliza en gráficos por ordenador y geometría computacional , es un tipo especial de volumen delimitador . Existen varios algoritmos de construcción de esferas delimitadoras rápidos y simples con un alto valor práctico en aplicaciones de gráficos por ordenador en tiempo real. ^[1]

En estadística e investigación de operaciones , los objetos son típicamente puntos y, generalmente, la esfera de interés es la esfera mínima delimitadora , es decir, la esfera con el radio mínimo entre todas las esferas delimitadoras. Se puede demostrar que dicha esfera es única: si hay dos, entonces los objetos en cuestión se encuentran dentro de su intersección. Pero una intersección de dos esferas no coincidentes de igual radio está contenida en una esfera de radio menor.

El problema de calcular el centro de una esfera delimitante mínima también se conoce como " problema euclidiano de 1 centro no ponderado ".

Aplicaciones

Agrupamiento

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

En el análisis estadístico, la dispersión de los puntos de datos dentro de una esfera puede atribuirse a un error de medición o a procesos naturales (normalmente térmicos), en cuyo caso el grupo representa una perturbación de un punto ideal. En algunas 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 de operaciones, la agrupación de valores en un punto ideal también se puede utilizar para reducir el número de entradas con el fin de obtener valores aproximados para problemas NP-hard en un tiempo razonable. El punto elegido no suele ser el centro de la esfera, ya que este puede verse sesgado por valores atípicos, sino que se calcula algún tipo de ubicación promedio, como un punto de mínimos cuadrados, para representar la agrupación.

Algoritmos

Existen algoritmos exactos y aproximados para la solución del problema de la esfera delimitadora.

Programación lineal

Nimrod Megiddo estudió extensamente el problema de 1 centro 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 se tiene en cuenta la dimensión, la complejidad del tiempo de ejecución es , ^{[3] [4]} lo que resulta poco práctico para aplicaciones de alta dimensión. ${\displaystyle d}$ ${\displaystyle O(2^{O(d^{2})}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 , que nuevamente se reduce a para cualquier dimensión fija . El artículo proporciona resultados experimentales que demuestran su viabilidad en dimensiones superiores. ^[5] Un algoritmo determinista más reciente de Timothy Chan también se ejecuta en el tiempo, con una dependencia menor (pero aún exponencial) de la dimensión. ^[4] ${\displaystyle O((d+1)(d+1)!n)}$ ${\displaystyle O(n)}$ ${\displaystyle d}$ ${\displaystyle O(n)}$

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

Esfera delimitadora de Ritter

En 1990, Jack Ritter propuso un algoritmo simple para encontrar una esfera delimitadora no mínima. ^[7] Se utiliza ampliamente en diversas aplicaciones por su simplicidad. El algoritmo funciona de esta manera:

1. Seleccione un punto de , busque un punto en , que tenga la mayor distancia desde ; ${\displaystyle x}$ ${\displaystyle P}$ ${\displaystyle y}$ ${\displaystyle P}$ ${\displaystyle x}$
2. Busca un punto en , que tenga la mayor distancia desde . Coloca una bola inicial , con su centro como el punto medio de y , el radio como la mitad de la distancia entre y ; ${\displaystyle z}$ ${\displaystyle P}$ ${\displaystyle y}$ ${\displaystyle B}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle y}$ ${\displaystyle z}$
3. Si todos los puntos de están dentro de la esfera , obtenemos una esfera delimitadora. De lo contrario, supongamos que hay un punto fuera de la esfera y construimos una nueva esfera que cubre tanto el punto como la esfera anterior. Repita este paso hasta que todos los puntos estén cubiertos. ${\displaystyle P}$ ${\displaystyle B}$ ${\displaystyle p}$ ${\displaystyle p}$

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

Aproximación basada en el conjunto central

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

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

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

Solucionador exacto de Fischer

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. ^[10] El algoritmo es puramente combinatorio e implementa un esquema de pivote 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 encoge gradualmente hasta que no se puede encoger 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 aceleración importante. 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 exhibe problemas de estabilidad numérica en sus operaciones de punto flotante. ^[10] Una implementación en C++ del algoritmo está disponible como un proyecto de código abierto. ^[11]

Puntos extremos de la esfera óptima

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

Véase también

• Volumen delimitador
• Esfera circunscrita , círculo circunscrito

Referencias

1. Larsson, Thomas (2008), "Esferas delimitadoras de ajuste rápido y ajustado", SIGRAD 2008: Conferencia anual SIGRAD, Tema especial: Interacción, 27 y 28 de noviembre de 2008, Estocolmo, Suecia , Actas electrónicas de la conferencia de Linköping, vol. 34, Linköping, Suecia: Universidad de Linköping
2. "Currículo y publicaciones de Nimrod Megiddo".
3. Megiddo, Nimrod (1988). "Programación lineal en tiempo lineal cuando la dimensión es fija". Revista de la ACM . 33 (1): 114–147. doi : 10.1145/2422.322418 . S2CID  12686747.
4. Chan, Timothy (2018). "Algoritmos deterministas mejorados para programación lineal en dimensiones bajas". ACM Transactions on Algorithms . 14 (3): Artículo 30, 10 páginas. doi :10.1145/3155312. S2CID  9345339.
5. Welzl, Emo (1991), "Los discos envolventes más pequeños (bolas y elipsoides)", en Maurer, Hermann (ed.), Nuevos resultados y nuevas tendencias en informática: Graz, Austria, 20-21 de junio de 1991, Actas, Notas de clase en informática, vol. 555, Berlín, Alemania: Springer, págs. 359-370, doi :10.1007/BFb0038202, ISBN 3-540-54869-6, Sr.  1254721
6. CGAL 4.3 - Volúmenes delimitadores - Min_sphere_of_spheres_d, recuperado el 30 de marzo de 2014.
7. Ritter, Jack (1990), "Una esfera delimitadora eficiente", en Glassner, Andrew S. (ed.), Graphics Gems , San Diego, CA, EE. UU.: Academic Press Professional, Inc., págs. 301–303, ISBN 0-12-286166-3
8. Bādoiu, Mihai; Har-Peled, Sariel ; Indyk, Piotr (2002), "Agrupamiento aproximado mediante conjuntos básicos" (PDF) , Actas del trigésimo cuarto simposio anual de la ACM sobre teoría de la computación , Nueva York, NY, EE. UU.: ACM, págs. 250-257, CiteSeerX 10.1.1.4.9395 , doi :10.1145/509907.509947, MR  2121149, S2CID  5409535 
9. Kumar, Piyush; Mitchell, Joseph SB ; Yıldırım, E. Alper (2003), "Computing core-sets and approximation lowest enclosing hyperspheres in high dimensions", en Ladner, Richard E. (ed.), Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, Baltimore, MD, EE. UU., 11 de enero de 2003 , Filadelfia, PA, EE. UU.: SIAM, págs. 45–55
10. Fischer, Kaspar; Gärtner, Bernd; Kutz, Martin (2003), "Fast lowest-enclosing-ball computation in high dimensions" (PDF) , en Battista, Giuseppe Di; Zwick, Uri (eds.), Algorithms: ESA 2003, 11th Annual European Symposium, Budapest, Hungría, 16-19 de septiembre de 2003, Actas (PDF) , Lecture Notes in Computer Science, vol. 2832, Springer, Berlín, págs. 630–641, doi :10.1007/978-3-540-39658-1_57, ISBN 978-3-540-20064-2
11. Proyecto de código abierto Miniball

Enlaces externos

• Problema del círculo más pequeño que encierra: describe varios algoritmos para encerrar un conjunto de puntos, incluido el algoritmo de tiempo lineal de Megiddo