Esfera delimitadora

una esfera que contiene un conjunto de objetos

Para el problema plano, consulte Círculo delimitador .

Algunas instancias 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 -dimensional espacio , por ejemplo un conjunto de puntos, una esfera de delimitación , encerrando esfera o encerrando balón para ese conjunto es una -dimensional esfera sólida que contiene todos estos objetos.${\displaystyle d}$${\displaystyle d}$

Utilizada en gráficos por computadora y geometría computacional , una esfera delimitadora es un tipo especial de volumen delimitador . Hay varios algoritmos de construcción de esferas delimitadores rápidos y simples con un alto valor práctico en aplicaciones de gráficos por computadora en tiempo real. ^[1]

En estadística e investigación de operaciones , los objetos suelen ser puntos y, en general, la esfera de interés es la esfera delimitadora mínima , es decir, la esfera con un radio mínimo entre todas las esferas delimitadoras. Se puede probar que tal esfera es única: si hay dos de ellos, 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 menor radio.

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

Aplicaciones

Agrupación

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

En el análisis estadístico, la dispersión de puntos de datos dentro de una esfera puede atribuirse a errores de medición o procesos naturales (generalmente térmicos), en cuyo caso el grupo representa una perturbación de un punto ideal. En algunas circunstancias, este punto ideal se puede utilizar 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-difíciles en un tiempo razonable. El punto elegido no suele ser el centro de la esfera, ya que esto puede estar sesgado por valores atípicos, sino que se calcula alguna forma de ubicación promedio, como un punto de mínimos cuadrados, para representar el grupo.

Algoritmos

Existen algoritmos exactos y aproximados para resolver el problema de la esfera delimitante.

Programación lineal

Nimrod Megiddo estudió extensamente el problema de un centro y lo publicó al menos cinco veces en los años ochenta. ^[2] En 1983, propuso un algoritmo de " poda y búsqueda " que encuentra la esfera límite ó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 poco práctica para aplicaciones de alta dimensión. Megido utilizó este enfoque de programación lineal en tiempo lineal cuando la dimensión es fija.${\displaystyle O((d+1)(d+1)!n)}$

En 1991, Emo Welzl propuso un algoritmo aleatorio mucho más simple basado en la extensión de un algoritmo de programación lineal aleatorio de Raimund Seidel . Se ejecuta en el tiempo lineal esperado. El artículo proporciona resultados experimentales que demuestran su practicidad en dimensiones superiores. ^[3]

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

Esfera delimitadora de Ritter

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

1. Elija un punto desde , busque un punto en , que tenga la mayor distancia desde ;${\displaystyle x}$${\displaystyle P}$${\displaystyle y}$${\displaystyle P}$${\displaystyle x}$
2. Busque un punto en , que tenga la mayor distancia desde . Coloque 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 están dentro de la bola , entonces obtenemos una esfera delimitadora. De lo contrario, deje un punto fuera de la bola, construya una nueva bola que cubra tanto el punto como la bola anterior. Repita este paso hasta cubrir todos los puntos.${\displaystyle P}$${\displaystyle B}$${\displaystyle p}$${\displaystyle p}$

El algoritmo de Ritter se ejecuta en el tiempo en entradas que consisten en puntos en el espacio dimensional, lo que lo hace muy eficiente. Sin embargo, solo da un resultado aproximado que suele ser de un 5% a un 20% más grande que el óptimo. ^{[ cita requerida ]}${\displaystyle O(nd)}$${\displaystyle n}$${\displaystyle d}$

Aproximación basada en conjuntos básicos

Bădoiu y col. presentó una aproximación al problema de la esfera delimitadora, ^[6] 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 coreset es un pequeño subconjunto, que una expansión de la solución en el subconjunto es una esfera delimitadora de todo el conjunto. El núcleo se construye de forma incremental agregando el punto más lejano al conjunto en cada iteración.${\displaystyle 1+\varepsilon }$

Kumar y col. mejoró este algoritmo de aproximación ^[7] 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 y col. (2003) propuso un solucionador exacto, aunque el algoritmo no tiene un tiempo de ejecución polinomial en el peor de los casos. ^[8] El algoritmo es puramente combinatorio e implementa un esquema pivotante similar al método simplex para la programación lineal., utilizado anteriormente en algunas heurísticas. Comienza con una gran esfera que cubre todos los puntos y se encoge gradualmente hasta que no se puede encoger más. El algoritmo presenta reglas de terminación correctas en casos de degeneraciones, ignoradas por autores anteriores; y manejo eficiente de soluciones parciales, lo que produce una mayor 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. ^[8] Una implementación C ++ del algoritmo está disponible como proyecto de código abierto. ^[9]

Esfera óptima de los puntos extremos

Larsson (2008) propuso el método de "esfera óptima de puntos extremos" con velocidad controlable a una aproximación de precisión 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 en cada vector en ; sirve como una variable de compensación de velocidad-precisión. Se aplica un solucionador exacto a los puntos extremos de estas proyecciones. El algoritmo luego itera sobre los puntos restantes, si los hay, haciendo crecer la esfera si es necesario. Para grandes, este método es órdenes de magnitud más rápido que los métodos exactos, al tiempo que da resultados comparables. Tiene un peor momento de . ^[1]${\displaystyle s}$${\displaystyle s}$${\displaystyle s}$${\displaystyle 2s}$${\displaystyle n}$${\displaystyle O(sn)}$

Ver también

• Límite de volumen
• Esfera circunscrita , círculo circunscrito

Referencias

1. Larsson, Thomas (2008), "Esferas delimitadoras rápidas y ajustadas" , SIGRAD 2008: The Annual SIGRAD Conference, Special Theme: Interaction, 27-28 de noviembre de 2008, Estocolmo, Suecia , Linköping Electronic Conference Proceedings, 34 , Linköping, Suecia: Universidad de Linköping
2. http://theory.stanford.edu/~megiddo/bio.html
3. Welzl, Emo (1991), "Discos envolventes más pequeños (bolas y elipsoides)", en Maurer, Hermann (ed.), Nuevos resultados y nuevas tendencias en informática: Graz, Austria, 20 al 21 de junio de 1991, Actas ( PDF) , Lecture Notes in Computer Science, 555 , Berlín, Alemania: Springer, págs. 359–370, doi : 10.1007 / BFb0038202 , MR 1254721  
4. CGAL 4.3 - Bounding Volumes - Min_sphere_of_spheres_d , consultado el 30 de marzo de 2014.
5. 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
6. Bādoiu, Mihai; Har-Peled, Sariel ; Indyk, Piotr (2002), " Agrupación aproximada a través de conjuntos básicos" (PDF) , Actas del trigésimo cuarto Simposio Anual de ACM sobre Teoría de la Computación , Nueva York, NY, EE.UU .: ACM, págs. 250-257, doi : 10.1145 / 509,907.509947 , MR 2.121.149 , S2CID 5409535   
7. Kumar, Piyush; Mitchell, Joseph SB ; Yıldırım, E. Alper (2003), "Computación de conjuntos de núcleos e hiperesferas envolventes más pequeñas aproximadas en dimensiones altas", en Ladner, Richard E. (ed.), Actas del quinto taller sobre ingeniería de algoritmos y experimentos, Baltimore, MD, EE. UU., 11 de enero de 2003 , Filadelfia, PA, EE. UU .: SIAM, págs. 45–55
8. Fischer, Kaspar; Gärtner, Bernd; Kutz, Martin (2003), "Cálculo rápido de la bola envolvente más pequeña en grandes dimensiones" (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, 2832 , Springer, Berlín, págs. 630– 641, doi : 10.1007 / 978-3-540-39658-1_57
9. proyecto de código abierto miniball

enlaces externos

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