Problema del círculo más pequeño

El problema del círculo más pequeño (también conocido como problema del círculo de cobertura 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 localización de instalaciones (el problema del 1-centro ) en el que se debe elegir la ubicación de una nueva instalación para brindar servicio a un número 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 son resolubles en tiempo lineal en el peor de los casos .

La mayoría de los enfoques geométricos para el problema buscan puntos que se encuentren 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 mínimo que cubre un conjunto S se puede determinar mediante, como máximo, tres puntos de S situados en el borde del círculo. Si se determina mediante solo dos puntos, el segmento de recta que une esos dos puntos debe ser un diámetro del círculo mínimo. Si se determina mediante tres puntos, el triángulo formado por esos tres puntos no es obtuso .

Como demostró Nimrod Megiddo , ^{[ 5 ]} el círculo envolvente mínimo se puede encontrar en tiempo lineal, y el mismo límite de tiempo lineal también se aplica a la esfera envolvente más pequeña en espacios euclidianos de cualquier dimensión constante. Su artículo también ofrece una breve descripción general de trabajos anteriores.${\displaystyle O(n^{3})}$y${\displaystyle O(n\log n)}$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 en${\displaystyle \Omega (n\log n)}$en 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 tiempo esperado.${\displaystyle O(n)}$, 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 pertenecer a esta clase, se demostró que la dependencia de la dimensión del factor constante en el${\displaystyle O(n)}$El límite de tiempo, que era factorial para el método de Seidel, podría reducirse a subexponencial . ^{[ 6 ]} El algoritmo de minidisco de Welzl se ha extendido para manejar divergencias de Bregman ^{[ 9 ]} que incluyen la distancia euclidiana al cuadrado.

El algoritmo de Megido

El algoritmo de Megiddo ^{[ 5 ]} se basa en la técnica llamada poda y búsqueda, que reduce el tamaño del problema eliminando${\textstyle {\frac {n}{16}}}$puntos innecesarios. Eso lleva a la recurrencia.${\displaystyle t(n)\leq t\left({\frac {15n}{16}}\right)+cn}$donación${\displaystyle t(n)=16cn}$.

El algoritmo es bastante complejo, como lo demuestra su elevada constante multiplicativa. La reducción requiere resolver dos veces un problema similar en el que el centro del círculo que se busca debe estar sobre 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 ubica el centro de la solución sin restricciones.

El${\textstyle {\frac {n}{16}}}$Los puntos que se descartan se encuentran de la siguiente manera: Los puntos P _i se organizan en pares que definen${\textstyle {\frac {n}{2}}}$líneas p _j como sus bisectrices . Se encuentra la mediana media p _m de las bisectrices en orden según sus direcciones (orientadas al mismo semiplano determinado por la bisectriz p ₁ ) y se forman pares de bisectrices, de modo que en cada par una bisectriz tenga una dirección como máximo p _m y la otra como mínimo p _m (la dirección p ₁ podría considerarse como −${\displaystyle \infty }$o +${\displaystyle \infty }$(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 ₁ se coloca para que pase por una intersección Q _x tal que hay${\textstyle {\frac {n}{8}}}$intersecciones en cada semiplano definido por la línea (posición media). La versión restringida del problema de cerramiento se ejecuta en la línea q' que determina el semiplano donde se encuentra el centro. La línea q ' en la _dirección pm se coloca para que pase por una intersección Qx _' de tal manera que haya${\textstyle {\frac {n}{16}}}$intersecciones en cada mitad del semiplano que no contiene la solución. La versión restringida del problema de cerco 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 que no está 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 de cerco. 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${\textstyle {\frac {n}{4}}}$puntos que conducen a la recurrencia

${\displaystyle t(n)\leq t\left({\frac {3n}{4}}\right)+cn}$

donación${\displaystyle t(n)=4cn}$.

El${\textstyle {\frac {n}{4}}}$Los puntos a descartar se encuentran de la siguiente manera: Los puntos P _i se organizan en pares. Para cada par, se encuentra la intersección Q _j de su bisectriz con la línea de restricción q (si esta intersección no existe, se puede eliminar un punto del par inmediatamente). Se encuentra la mediana M de los puntos Q _j en la línea q y en 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 semirrecta. 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 que encierra la solución del problema restringido. Este punto puede descartarse.

El semiplano donde se encuentra la solución sin restricciones puede determinarse mediante los puntos P _i en el límite de la solución circular con restricciones. (Basta con el primer y el último punto de la circunferencia en cada semiplano. Si el centro pertenece a su envolvente 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 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 ( de forma aleatoria y uniforme ). D := welzl( P − { p }, R ) si p está en D entonces devuelve Dreturn welzl( P − { p }, R ∪ { p })

^{Antes del resultado de Megiddo ,} que demostró 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 tiempo O( n⁴ ) probando los círculos determinados por todos los pares y tríos 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 envolvente y reduce repetidamente el círculo, reemplazando el par de puntos del límite, hasta encontrar 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 del límite en ese círculo. Cada paso del algoritmo incluye como uno de los dos puntos del límite un nuevo vértice de la envoltura convexa , por lo que si la envoltura tiene h vértices, este método puede implementarse para ejecutarse en tiempo O( nh ).
• Elzinga y Hearn ^{[ 11 ]} 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 tiempo de ejecución en el peor de los casos es O( ^h³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 en Fortran y C están disponibles en Hearn, Vijay y Nickel (1995) . ^{[ 13 ]}
• El problema de la esfera más pequeña puede formularse 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 proporcionar la solución del 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 primal-dual. ^{[ 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 más pequeño que lo encierra debe ser un vértice del diagrama de Voronoi del punto más alejado del conjunto de puntos de entrada. 

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 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ínimo corresponde al caso en 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 algoritmos de programación lineal de dimensión acotada, aunque en la literatura también son frecuentes algoritmos más lentos. ^{[ 15 ] [ 18 ] [ 19 ]}

La bola envolvente más pequeña de un conjunto finito de puntos se ha estudiado en geometría riemanniana, incluyendo variedades de Cartan-Hadamard . ^{[ 20 ]}

• Esfera delimitadora
• Problema de 1 centro
• Círculo circunscrito
• Cadena más cercana
• Teorema de Jung
• Árbol de diámetro mínimo que abarca

• El código de bolas de contención 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 es una implementación de código abierto de un algoritmo para el problema de la bola más pequeña que contiene un objeto, para dimensiones bajas y moderadamente altas.