El problema del círculo más pequeño (también conocido como problema del círculo envolvente mínimo , problema del círculo delimitador , problema del círculo delimitador mínimo , problema del círculo envolvente más pequeño ) es un problema de geometría computacional que consiste en calcular el círculo más pequeño que contiene todos los puntos de un conjunto dado en el plano euclidiano . El problema correspondiente en el espacio n -dimensional , el problema de la esfera delimitadora más pequeña , consiste en calcular la n -esfera más pequeña que contiene todos los puntos de un conjunto dado. [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 plano es un ejemplo de un problema de ubicación de instalaciones (el problema de 1 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 recorrer 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 acotada se pueden resolver en un tiempo lineal en el peor de los casos .
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:
Como demostró Nimrod Megiddo [5] , el círculo mínimo que lo encierra se puede encontrar en tiempo lineal, y el mismo límite de tiempo lineal también se aplica a la esfera más pequeña que lo encierra en espacios euclidianos de cualquier dimensión constante. Su artículo también ofrece una breve descripción general de algoritmos y ecuaciones anteriores ; [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 en el mejor de los casos) era falsa. [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 basado 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 el límite de tiempo, que era factorial para el método de Seidel, podía reducirse a subexponencial . [6] El algoritmo del minidisco de Welzl se ha extendido para manejar divergencias de Bregman [9] que incluyen la distancia euclidiana al cuadrado.
El algoritmo de Megiddo [10] se basa en la técnica denominada poda y búsqueda, que reduce el tamaño del problema eliminando puntos innecesarios. Esto lleva a que la recurrencia dé .
El algoritmo es bastante complicado y se refleja en su gran constante multiplicativa. La reducción necesita resolver dos veces el mismo problema 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 sin restricciones o se utiliza para determinar el semiplano donde se encuentra el centro de la solución sin restricciones.
Los puntos a descartar se encuentran de la siguiente manera: Los puntos P i se disponen en pares que definen las líneas p j como sus bisectrices . Se encuentra la media mediana p m de las bisectrices en orden por sus direcciones (orientadas al mismo semiplano determinado por la bisectriz p 1 ) y se hacen pares de bisectrices, de modo que en cada par una bisectriz tenga dirección como máximo p m y la otra como mínimo 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 en el k -ésimo par.
La línea q en la dirección p 1 se coloca para pasar por una intersección Q x de modo que haya intersecciones en cada semiplano definido por la línea (posición media). La versión restringida del problema de encierro se ejecuta en la línea q' que determina el semiplano donde se ubica el centro. La línea q ′ en la dirección p m se coloca para pasar por una intersección Q x' de modo que haya intersecciones en cada mitad del semiplano que no contenga la solución. La versión restringida del problema de encierro se ejecuta en la línea q ′ que junto con q determina el cuadrante donde se ubica el centro. Consideramos los puntos Q k en el cuadrante no contenido 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 que encierra. 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 .
Los puntos a descartar se encuentran de la siguiente manera: Los puntos P i se disponen 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 eliminar un punto del par inmediatamente). Se encuentra la mediana M de los puntos Q j en la línea q y en un tiempo O ( n ) se determina qué semirrecta 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 semirrecta 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 sin restricciones se puede determinar mediante los puntos P i en el límite de la solución circular con restricciones. (El primer y el último punto del círculo en cada semiplano son suficientes. Si el centro pertenece a su envoltura convexa , se trata de una solución sin restricciones; de lo contrario, la dirección hacia el borde más cercano determina el semiplano de la solución sin restricciones).
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 recursivamente 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 todo P y se devuelve.
De lo contrario, el punto p debe estar en el límite del círculo resultante. Se recurre, pero con el conjunto R de puntos que se sabe que están en el límite como parámetro adicional.
La recursión 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 el circuncírculo 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 tamaño 3 (en 2D, o 4 en 3D) porque los puntos restantes en P deben estar dentro del círculo descrito por R.
El 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 entonces devuelve trivial( R ) elige p en P ( aleatoria y uniformemente ) D := welzl( P − { p }, R ) si p está en D entonces devuelve D devuelve welzl( P − { p }, R ∪ { p })
El artículo de Welzl afirma que es suficiente permutar aleatoriamente la entrada al inicio, en lugar de realizar elecciones aleatorias independientes de p en cada recursión.
También afirma que el rendimiento se mejora al reordenar dinámicamente los puntos de modo que aquellos que se encuentran fuera de un círculo se consideren antes, pero esto requiere un cambio en la estructura del algoritmo para almacenar P como "global".
Antes del resultado de Megiddo, que demostraba que el problema del círculo más pequeño se podía resolver en tiempo lineal, aparecieron en la literatura varios algoritmos de mayor complejidad. Un algoritmo ingenuo resuelve el problema en tiempo O( n 4 ) 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ínima 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 ponderada máxima (es decir, la distancia multiplicada por el peso correspondiente) a cualquier punto. El problema original (no ponderado) del círculo de cobertura mínima corresponde al caso en el que todos los pesos son iguales a 1. 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. [16] [19] [20]
La bola envolvente más pequeña de un conjunto de puntos finitos se ha estudiado en geometría de Riemann, incluidas las variedades de Cartan-Hadamard. [21]
