Problema del círculo mínimo
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9c/Smallest_circle_problem.svg/300px-Smallest_circle_problem.svg.png)
El problema del círculo mínimo (también conocido como el problema del círculo de recubrimiento mínimo) es una cuestión matemática, consistente en calcular la circunferencia más pequeña que contiene todo un conjunto de puntos dado en el plano. El problema correspondiente en el espacio n-dimensional, implica determinar la n-esfera más pequeña que contiene todos los puntos de un conjunto dado.[1] El problema del círculo mínimo fue propuesto inicialmente por el matemático inglés James Joseph Sylvester en 1857.[2]
En el plano es un ejemplo de un problema de localización de servicios (el problema del 1-centro) en el que se debe elegir la ubicación de una nueva instalación para proporcionar servicio a un determinado número de clientes, minimizando la distancia más larga que cualquier cliente debe recorrer para alcanzar el nueva instalación.[3] Tanto el problema de círculo mínimo en el plano como el problema de la esfera mínima en cualquier espacio de dimensión superior finita se pueden resolver con rutinas en tiempo lineal.
Caracterización
[editar]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 por un máximo de tres puntos en S, que se encuentran en el límite del círculo. Si solo está determinado por dos puntos, entonces el segmento de línea que une esos dos puntos debe ser un diámetro del círculo mínimo. Si está determinado por tres puntos, entonces el triángulo formado por esos tres puntos no es obtuso.
Demostración de que el disco de cobertura mínimo es único |
Sea P un conjunto cualquiera de puntos en el plano, y supóngase que hay dos discos más pequeños que recubren P, con centros en y . Sea r su radio compartido y sea la distancia entre sus centros. Entonces, 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 el centro y el radio , como se muestra en la siguiente imagen: Como r es mínimo, entonces , lo que significa que , por lo que los discos son idénticos.[4] |
Soluciones en tiempo lineal
[editar]Como Nimrod Megiddo demostró,[5] el círculo delimitador mínimo se puede encontrar en tiempo lineal, y el mismo límite de tiempo lineal también se aplica a la esfera mínima envolvente en espacios euclidianos de cualquier dimensión finita.
Emo Welzl[6] propuso un algoritmo aleatorio simple para el problema del círculo mínimo de cobertura, que se ejecuta en el tiempo esperado , basado en un algoritmo de programación lineal de Raimund Seidel. Este algoritmo se presenta a continuación.
Posteriormente, el problema del círculo mínimo se incluyó en una clase general de problemas tipo LP, que se puede resolver con algoritmos como el basado en la programación lineal de Welzl. Como consecuencia de pertenecer a esta clase, se demostró que la dependencia de la dimensión del factor constante en el límite de tiempo de , que era factorial para el método de Seidel, podría reducirse a subexponencial, mientras que todavía se mantiene solo la dependencia lineal de N.[7]
El algoritmo de Welzl
[editar]El algoritmo es recursivo y toma como argumentos dos conjuntos (finitos) de puntos P y R; calcula el círculo delimitador más pequeño de la unión de P y de R, siempre que cada punto de R sea uno de los puntos límite del eventual círculo delimitador más pequeño. Por lo tanto, el problema del círculo circundante más pequeño original puede resolverse llamando al algoritmo con P igual al conjunto de puntos que se van a encerrar y R igual al conjunto vacío; como el algoritmo se llama recursivamente, ampliará el conjunto R mediante sucesivas llamadas recursivas hasta que incluya todos los puntos límite del círculo.
El algoritmo procesa los puntos de P en un orden aleatorio, manteniendo como lo hace el conjunto S de puntos procesados y el círculo más pequeño D que encierra la unión S ∪ R. En cada paso, prueba si el siguiente punto p para ser procesado está en D; si no, el algoritmo reemplaza el D por el resultado de una llamada recursiva del algoritmo en los conjuntos S y R ∪ p. En función de si el círculo fue reemplazado o no, p se incluye en el conjunto S. El procesamiento de cada punto, por lo tanto, consiste en probar en tiempo constante si el punto pertenece a un solo círculo y posiblemente realizar una llamada recursiva al algoritmo. Se puede demostrar que el tiempo total es lineal.
algorithm welzl:[8] input: Finite sets P and R of points in the plane output: Minimal disk enclosing P with R on the boundary, or undefined if no such disk exists if P is empty or |R| ≥ 3: if |R| = 1: (we do this to support multisets with duplicate points) (we assume that a circle with a radius of zero can exist) p := R[0] return circle(p, 0) else if |R| = 2: (we do this to support multisets with duplicate points) (we use that the smallest circle between two points has a center at their midpoint) (and the segment that passes through them is a diameter of the circle) p0 := R[0] p1 := R[1] center := midpoint(p0, p1) diameter := distance(p0, p1) return circle(center, diameter / 2) else if the points of R are cocircular: return the ball they determine else: return undefined choose p in P (randomly and uniformly) D := welzl(P - { p }, R) if p is in D: return D return welzl(P - { p }, R ∪ { p })
Otros algoritmos
[editar]Antes del resultado de Megiddo que muestra que el problema del círculo mímo se puede resolver en tiempo lineal, se idearon varios algoritmos de mayor complejidad. Un algoritmo ingenuo resuelve el problema en el tiempo O (n4) probando los círculos determinados por todos los pares y triples de puntos.
- Un algoritmo de Chrystal y Peirce aplica una estrategia 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 límite, hasta que se encuentra un círculo óptimo. Chakraborty y Chaudhuri[9] 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 de la envolvente convexa, por lo que si el contorno tiene h vértices, este método puede implementarse para ejecutarse en el tiempo O (nh).
- Elzinga y Hearn[10] describieron un algoritmo que mantiene un círculo de cobertura para un subconjunto de los puntos. En cada paso, un punto no cubierto por la esfera actual se utiliza 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 (h3n), los autores informan que se ejecutó en tiempo lineal en sus experimentos. La complejidad del método ha sido analizada por Drezner y Shelah.[11] Ambos códigos Fortran y C están disponibles en Hearn, Vijay y Nickel (1995).[12]
- El problema de la esfera mínima 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 lo tanto, cualquier algoritmo de dirección factible puede dar la solución al problema.[13] Hearn y Vijay[14] demostraron que el enfoque de dirección factible elegido por Jacobsen es equivalente al algoritmo de Chrystal-Peirce.
- El dual a este programa cuadrático también se puede formular explícitamente:[15] un algoritmo de Lawson[16] se puede describir de esta manera como un algoritmo dual primario.[14]
- Shamos y Hoey[17] propusieron un algoritmo de tiempo O (n log n) para el problema basado en la observación de que el centro del círculo delimitador más pequeño debe ser un vértice del punto más alejado de los polígonos de Thiessen del conjunto de puntos de entrada.
Variaciones ponderadas del problema
[editar]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 original mínimo del círculo de cobertura puede recuperarse 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 limitada, utilizando enfoques estrechamente relacionados con los algoritmos de programación lineal de acotación limitada, aunque los algoritmos más lentos vuelven a ser frecuentes en la literatura.[14][18][19]
Véase también
[editar]Referencias
[editar]- ↑ a b Elzinga, J.; Hearn, D. W. (1972), «The minimum covering sphere problem», Management Science 19: 96-104, doi:10.1287/mnsc.19.1.96.
- ↑ Sylvester, J. J. (1857), «A question in the geometry of situation», Quarterly Journal of Mathematics 1: 79..
- ↑ Francis, R. L.; McGinnis, L. F.; White, J. A. (1992), Facility Layout and Location: An Analytical Approach (2nd edición), Englewood Cliffs, N.J.: Prentice–Hall, Inc...
- ↑ Welzl, 1991, p. 2.
- ↑ Megiddo, Nimrod (1983), «Linear-time algorithms for linear programming in R3 and related problems», SIAM Journal on Computing 12 (4): 759-776, MR 721011, doi:10.1137/0212052..
- ↑ Welzl, Emo (1991), «Smallest enclosing disks (balls and ellipsoids)», en Maurer, H., ed., New Results and New Trends in Computer Science, Lecture Notes in Computer Science 555, Springer-Verlag, pp. 359-370, doi:10.1007/BFb0038202..
- ↑ Matoušek, Jiří; Sharir, Micha; Welzl, Emo (1996), «A subexponential bound for linear programming», Algorithmica 16: 498-516, doi:10.1007/BF01940877..
- ↑ Welzl, 1991.
- ↑ Chakraborty, R. K.; Chaudhuri, P. K. (1981), «Note on geometrical solutions for some minimax location problems», Transportation Science 15: 164-166, doi:10.1287/trsc.15.2.164..
- ↑ Elzinga, J.; Hearn, D. W. (1972), «Geometrical solutions for some minimax location problems», Transportation Science 6: 379-394, doi:10.1287/trsc.6.4.379..
- ↑ Drezner, Z.; Shelah, S. (1987), «On the complexity of the Elzinga–Hearn algorithm for the 1-center problem», Mathematics of Operations Research 12 (2): 255-261, JSTOR 3689688, doi:10.1287/moor.12.2.255..
- ↑ Hearn, D. W.; Vijay, J.; Nickel, S. (1995), «Codes of geometrical algorithms for the (weighted) minimum circle problem», European Journal of Operational Research 80: 236-237, doi:10.1016/0377-2217(95)90075-6..
- ↑ Jacobsen, S. K. (1981), «An algorithm for the minimax Weber problem», European Journal of Operational Research 6: 144-148, doi:10.1016/0377-2217(81)90200-9..
- ↑ a b c Hearn, D. W.; Vijay, J. (1982), «Efficient algorithms for the (weighted) minimum circle problem», Operations Research 30 (4): 777-795, doi:10.1287/opre.30.4.777..
- ↑ Elzinga, J.; Hearn, D. W.; Randolph, W. D. (1976), «Minimax multifacility location with Euclidean distances», Transportation Science 10: 321-336, doi:10.1287/trsc.10.4.321..
- ↑ Lawson, C. L. (1965), «The smallest covering cone or sphere», Sociedad de Matemáticas Aplicadas e Industriales 7 (3): 415-417, doi:10.1137/1007084..
- ↑ Shamos, M. I.; Hoey, D. (1975), «Closest point problems», Proceedings of 16th Annual IEEE Symposium on Foundations of Computer Science, pp. 151-162, doi:10.1109/SFCS.1975.8..
- ↑ Megiddo, N. (1983), «The weighted Euclidean 1-center problem», Mathematics of Operations Research 8: 498-504, doi:10.1287/moor.8.4.498..
- ↑ Megiddo, N.; Zemel, E. (1986), «An O(n log n) randomizing algorithm for the weighted Euclidean 1-center problem», Journal of Algorithms 7: 358-368, doi:10.1016/0196-6774(86)90027-1..
Enlaces externos
[editar]- El código de bola 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 fuente abierta de un algoritmo para el problema de bola envolvente mínima para dimensiones bajas y moderadamente altas