El problema más pequeño círculo (también conocido como mínimo cubriendo problema círculo , delimita problema círculo , más pequeño que encierra problema círculo ) es un problema matemático de calcular el más pequeño círculo que contiene toda de un determinado conjunto de puntos en el plano euclidiano . El problema correspondiente en n espacio dimensional , la más pequeña de delimitación esfera problema, es calcular el más pequeño n -sphere que contiene todos los de un conjunto dado de puntos. [1]El problema del círculo más pequeño fue propuesto inicialmente por el matemático inglés James Joseph Sylvester en 1857. [2]
El problema del círculo más pequeño en el avión es un ejemplo de un problema de ubicación de una instalación (el problema de un centro ) en el que se debe elegir la ubicación de una nueva instalación para brindar servicio a una cantidad de clientes, minimizando la distancia más lejana que cualquier cliente. debe viajar para llegar a la nueva instalación. [3] Tanto el problema del círculo más pequeño en el plano como el problema de la esfera delimitadora más pequeña en cualquier espacio de dimensión superior de dimensión limitada se pueden resolver en el peor de los casos en tiempo lineal .
Caracterización
La mayoría de los enfoques geométricos para el problema buscan puntos que se encuentran en el límite del círculo mínimo y se basan en los siguientes hechos simples:
- El círculo de cobertura mínimo es único.
- El círculo de cobertura mínimo de un conjunto S puede determinarse como máximo por tres puntos en S que se encuentran en el límite del círculo. Si está determinado por solo dos puntos, entonces el segmento de línea que une esos dos puntos debe tener un diámetro del círculo mínimo. Si está determinado por tres puntos, entonces el triángulo que consta de esos tres puntos no es obtuso .
Prueba de que el disco de cobertura mínimo es único |
---|
Sea P cualquier conjunto de puntos en el plano, y suponga que hay dos discos envolventes de P más pequeños , con centros en y . Dejarser su radio compartido , y dejarsea la distancia entre sus centros. Dado que P es un subconjunto de ambos discos, es un subconjunto de su intersección . Sin embargo, su intersección está contenida dentro del disco con centro y radio , como se muestra en la siguiente imagen: Dado que r es mínimo, debemos tener, significado , por lo que los discos son idénticos. [4] |
Soluciones de tiempo lineal
Como mostró Nimrod Megiddo , [5] el círculo circundante mínimo se puede encontrar en el tiempo lineal, y el mismo límite de tiempo lineal también se aplica a la esfera circundante más pequeña en los espacios euclidianos de cualquier dimensión constante. Su artículo también ofrece una breve descripción de y algoritmos; [6] al hacerlo, Megiddo demostró que la conjetura de Shamos y Hoey - que una solución al problema del círculo más pequeño era computable enen el mejor de los casos, era falso. [7]
Emo Welzl [8] propuso un algoritmo aleatorio simple para el problema del círculo de cobertura mínimo que se ejecuta en el tiempo esperado. , basado en un algoritmo de programación lineal de Raimund Seidel .
Posteriormente, el problema del círculo más pequeño se incluyó en una clase general de problemas de tipo LP que pueden resolverse mediante algoritmos como el de Welzl basados en programación lineal. Como consecuencia de la pertenencia a esta clase, se demostró que la dependencia de la dimensión del factor constante en elEl límite de tiempo, que era factorial para el método de Seidel, podría reducirse a subexponencial . [6]
El algoritmo de Megido
El algoritmo de Megido [9] se basa en la técnica denominada poda y búsqueda, que reduce el tamaño del problema al eliminarpuntos innecesarios. Que lleva a la recurrencia donación .
El algoritmo es bastante complicado y se refleja en su gran constante multiplicativa. La reducción debe resolver dos veces el problema similar en el que el centro del círculo circundante buscado está restringido a estar en una línea dada . La solución del subproblema es la solución del problema no restringido o se usa para determinar el semiplano donde se encuentra el centro de solución no restringido.
La Los puntos a descartar se encuentran de la siguiente manera: Los puntos P i se organizan en pares, lo que definelíneas p j como sus bisectrices . Se calcula la mediana p m de las bisectrices en orden por sus direcciones (orientadas al mismo semiplano determinado por la bisectriz p 1 ) y se forman pares de bisectrices, de modo que en cada par una bisectriz tenga una dirección como máximo p my el otro al menos p m (la dirección p 1 podría considerarse como - o +según nuestras necesidades.) Sea Q k la intersección de las bisectrices del k -ésimo par.
La recta q en la dirección p 1 se coloca para pasar por una intersección Q x tal que hayintersecciones en cada semiplano definido por la línea (posición mediana). La versión restringida del problema de encerramiento se ejecuta en la línea q 'que determina el semiplano donde se encuentra el centro. La recta q ′ en la dirección p m se coloca para pasar por una intersección Q x ' tal que hayintersecciones en cada mitad del semiplano que no contienen la solución. La versión restringida del problema circundante se ejecuta en la línea q ′ que junto con q determina el cuadrante donde se encuentra el centro. Consideramos que los puntos Q k en el cuadrante no están contenidos en un semiplano que contiene la solución. Una de las bisectrices del par que define Q k tiene la dirección que asegura cuál de los puntos P i que definen la bisectriz está más cerca de cada punto en el cuadrante que contiene el centro del círculo circundante. Este punto podría descartarse.
La versión restringida del algoritmo también se resuelve mediante la técnica de poda y búsqueda, pero reduciendo el tamaño del problema mediante la eliminación de puntos que conducen a la recurrencia
donación .
La los puntos a descartar se encuentran de la siguiente manera: Los puntos P i se ordenan en pares. Para cada par, se encuentra la intersección Q j de su bisectriz con la línea restrictiva q (si esta intersección no existe, podríamos quitar un punto del par inmediatamente). Se encuentra la mediana M de los puntos Q j en la línea q y en O ( n ) tiempo se determina qué línea media de q que comienza en M contiene la solución del problema restringido. Consideramos los puntos Q j de la otra mitad. Sabemos cuál de los puntos P i que definen Q j está más cerca de cada punto de la línea media que contiene el centro del círculo circundante de la solución del problema restringido. Este punto podría descartarse.
El semiplano donde se encuentra la solución no restringida podría ser determinado por los puntos P i en el límite de la solución del círculo restringido. (El primer y último punto del círculo en cada semiplano es suficiente. Si el centro pertenece a su casco convexo , es una solución sin restricciones; de lo contrario, la dirección al borde más cercano determina el semiplano de la solución sin restricciones).
Algoritmo de Welzl
El algoritmo es recursivo .
La entrada inicial es un conjunto P de puntos. El algoritmo selecciona un punto p de forma aleatoria y uniforme de P , y encuentra de forma recursiva el círculo mínimo que contiene P - { p }, es decir, todos los demás puntos de P excepto p . Si el círculo devuelto también encierra p , es el círculo mínimo para la totalidad de P y se devuelve.
De lo contrario, el punto p debe estar en el límite del círculo de resultado. Se repite, pero con el conjunto R de puntos que se sabe que están en el límite como parámetro adicional.
La recursividad termina cuando P está vacío y se puede encontrar una solución a partir de los puntos en R : para 0 o 1 puntos la solución es trivial, para 2 puntos el círculo mínimo tiene su centro en el punto medio entre los dos puntos, y para 3 puntos el círculo es la circunferencia del triángulo descrito por los puntos. (En tres dimensiones, 4 puntos requieren el cálculo de la circunsfera de un tetraedro ).
La recursión también puede terminar cuando R tiene un tamaño de 3 (en 2D, o 4 en 3D) porque los puntos restantes en P deben estar dentro del círculo descrito por R .
algoritmo welzl es [8] entrada: Conjuntos finitos P y R de puntos en el plano | R | ≤ 3. salida: Disco mínimo que encierra P con R en el límite. si P está vacío o | R | = 3 luego devuelve trivial ( R ) elige p en P ( aleatoria y uniformemente ) D: = welzl ( P - { p }, R ) si p está en D entonces devuelve D return welzl ( P - { p }, R ∪ { p })
El artículo de Welzl establece que es suficiente permutar aleatoriamente la entrada al principio, en lugar de realizar elecciones aleatorias independientes de p en cada recursión.
También establece que el rendimiento se mejora reordenando dinámicamente los puntos para que aquellos que se encuentran fuera de un círculo se consideren posteriormente antes, pero esto requiere un cambio en la estructura del algoritmo para almacenar P como un "global".
Otros algoritmos
Antes del resultado de Megido que mostraba que el problema del círculo más pequeño puede resolverse en tiempo lineal, aparecieron en la literatura varios algoritmos de mayor complejidad. Un algoritmo ingenuo resuelve el problema en el tiempo O ( n 4 ) probando los círculos determinados por todos los pares y triples de puntos.
- Un algoritmo de Chrystal y Peirce aplica una estrategia de optimización local que mantiene dos puntos en el límite de un círculo circundante y reduce repetidamente el círculo, reemplazando el par de puntos del límite, hasta que se encuentra un círculo óptimo. Chakraborty y Chaudhuri [10] proponen un método de tiempo lineal para seleccionar un círculo inicial adecuado y un par de puntos límite en ese círculo. Cada paso del algoritmo incluye como uno de los dos puntos límite un nuevo vértice del casco convexo , por lo que si el casco tiene h vértices, este método se puede implementar para que se ejecute en el tiempo O ( nh ).
- Elzinga y Hearn [11] describieron un algoritmo que mantiene un círculo de cobertura para un subconjunto de puntos. En cada paso, se utiliza un punto no cubierto por la esfera actual para encontrar una esfera más grande que cubra un nuevo subconjunto de puntos, incluido el punto encontrado. Aunque su peor tiempo de ejecución es O ( h 3 n ), los autores informan que se ejecutó en tiempo lineal en sus experimentos. La complejidad del método ha sido analizada por Drezner y Shelah. [12] Los códigos Fortran y C están disponibles en Hearn, Vijay & Nickel (1995) . [13]
- El problema de la esfera más pequeña se puede formular como un programa cuadrático [1] definido por un sistema de restricciones lineales con una función objetivo cuadrática convexa. Por tanto, cualquier algoritmo de dirección factible puede dar la solución al problema. [14] Hearn y Vijay [15] demostraron que el enfoque de dirección factible elegido por Jacobsen es equivalente al algoritmo de Chrystal-Peirce.
- El dual de este programa cuadrático también puede formularse explícitamente; [16] un algoritmo de Lawson [17] puede describirse de esta manera como un algoritmo dual primario. [15]
- Shamos y Hoey [7] propusieron un algoritmo de tiempo O ( n log n ) para el problema basado en la observación de que el centro del círculo envolvente más pequeño debe ser un vértice del diagrama de Voronoi del punto más lejano del conjunto de puntos de entrada.
Variantes ponderadas del problema
La versión ponderada del problema del círculo de cobertura mínimo toma como entrada un conjunto de puntos en un espacio euclidiano, cada uno con pesos; el objetivo es encontrar un único punto que minimice la distancia máxima ponderada a cualquier punto. El problema del círculo de cobertura mínimo original se puede recuperar estableciendo todos los pesos en el mismo número. Al igual que con el problema no ponderado, el problema ponderado puede resolverse en tiempo lineal en cualquier espacio de dimensión acotada, utilizando enfoques estrechamente relacionados con los algoritmos de programación lineal de dimensión acotada, aunque los algoritmos más lentos son nuevamente frecuentes en la literatura. [15] [18] [19]
Ver también
- Esfera delimitadora
- Problema de 1 centro
- Círculo circunscrito
- Cadena más cercana
- Teorema de Jung
Referencias
- ↑ a b Elzinga, J .; Hearn, DW (1972), "El problema de la esfera de cobertura mínima", Management Science , 19 : 96-104, doi : 10.1287 / mnsc.19.1.96
- ^ Sylvester, JJ (1857), "pregunta A en la geometría de la situación", Quarterly Journal of Mathematics , 1 : 79.
- ^ Francis, RL; McGinnis, LF; White, JA (1992), Disposición y ubicación de las instalaciones: un enfoque analítico (2ª ed.), Englewood Cliffs, Nueva Jersey: Prentice – Hall, Inc..
- ^ Welzl 1991 , p. 2.
- ^ Megiddo, Nimrod (1983), "Algoritmos de tiempo lineal para programación lineal en R 3 y problemas relacionados", SIAM Journal on Computing , 12 (4): 759–776, doi : 10.1137 / 0212052 , MR 0721011.
- ^ a b Matoušek, Jiří ; Sharir, Micha ; Welzl, Emo (1996), "Un límite subexponencial para la programación lineal" (PDF) , Algorithmica , 16 (4–5): 498–516, CiteSeerX 10.1.1.46.5644 , doi : 10.1007 / BF01940877.
- ^ a b Shamos, MI ; Hoey, D. (1975), "Problemas más cercanos", Actas del 16 ° Simposio anual del IEEE sobre fundamentos de la informática , págs. 151-162, doi : 10.1109 / SFCS.1975.8
- ^ a b Welzl, Emo (1991), "Discos envolventes más pequeños (bolas y elipsoides)", en Maurer, H. (ed.), New Results and New Trends in Computer Science , Lecture Notes in Computer Science, 555 , Springer-Verlag, págs. . 359–370, CiteSeerX 10.1.1.46.1450 , doi : 10.1007 / BFb0038202 , ISBN 978-3-540-54869-0.
- ^ Megiddo, Nimrod (1983), "Algoritmos de tiempo lineal para programación lineal en R 3 y problemas relacionados", SIAM Journal on Computing , 12 (4): 759–776, doi : 10.1137 / 0212052 , MR 0721011.
- ^ Chakraborty, RK; Chaudhuri, PK (1981), "Nota sobre soluciones geométricas para algunos problemas de ubicación minimax", Transportation Science , 15 (2): 164-166, doi : 10.1287 / trsc.15.2.164.
- ^ Elzinga, J .; Hearn, DW (1972), "Soluciones geométricas para algunos problemas de ubicación de minimax", Transportation Science , 6 (4): 379–394, doi : 10.1287 / trsc.6.4.379.
- ^ Drezner, Z .; Shelah, S. (1987), "Sobre la complejidad del algoritmo de Elzinga-Hearn para el problema de un centro", Mathematics of Operations Research , 12 (2): 255-261, doi : 10.1287 / moor.12.2.255 , JSTOR 3689688.
- ^ Hearn, DW; Vijay, J .; Nickel, S. (1995), "Códigos de algoritmos geométricos para el problema del círculo mínimo (ponderado)", European Journal of Operational Research , 80 : 236-237, doi : 10.1016 / 0377-2217 (95) 90075-6.
- ^ Jacobsen, SK (1981), "Un algoritmo para el problema minimax Weber", European Journal of Operational Research , 6 (2): 144–148, doi : 10.1016 / 0377-2217 (81) 90200-9.
- ^ a b c Hearn, DW; Vijay, J. (1982), "Algoritmos eficientes para el problema del círculo mínimo (ponderado)", Investigación de operaciones , 30 (4): 777–795, doi : 10.1287 / opre.30.4.777.
- ^ Elzinga, J .; Hearn, DW; Randolph, WD (1976), "Ubicación de múltiples instalaciones Minimax con distancias euclidianas", Transportation Science , 10 (4): 321–336, doi : 10.1287 / trsc.10.4.321.
- ^ Lawson, CL (1965), "El cono o esfera de cobertura más pequeño", SIAM Review , 7 (3): 415–417, doi : 10.1137 / 1007084.
- ^ Megiddo, N. (1983), "El problema euclidiano ponderado de un centro", Mathematics of Operations Research , 8 (4): 498–504, doi : 10.1287 / moor.8.4.498.
- ^ Megido, N .; Zemel, E. (1986), "Un algoritmo de aleatorización O ( n log n ) para el problema euclidiano ponderado de 1 centro", Journal of Algorithms , 7 (3): 358-368, doi : 10.1016 / 0196-6774 (86 ) 90027-1.
enlaces externos
- El código de bola envolvente más pequeño de Bernd Gärtner
- CGAL el paquete Min_sphere_of_spheres de la Biblioteca de algoritmos de geometría computacional (CGAL)
- Miniball una implementación de código abierto de un algoritmo para el problema de la bola envolvente más pequeña para dimensiones bajas y moderadamente altas