Problema del círculo mínimo
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.
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: 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
[4] 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
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.
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.
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.
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.
