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. El problema del círculo mínimo fue propuesto inicialmente por el matemático inglés James Joseph Sylvester en 1857.

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. 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 
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.

Soluciones en tiempo lineal 
Como Nimrod Megiddo demostró, 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 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.

El algoritmo de Welzl 

El algoritmo es recursivo y toma como argumentos dos conjuntos (finitos) de puntos  y ; calcula el círculo delimitador más pequeño de la unión de  y de , siempre que cada punto de  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  igual al conjunto de puntos que se van a encerrar y  igual al conjunto vacío; como el algoritmo se llama recursivamente, ampliará el conjunto  mediante sucesivas llamadas recursivas hasta que incluya todos los puntos límite del círculo.

El algoritmo procesa los puntos de  en un orden aleatorio, manteniendo como lo hace el conjunto  de puntos procesados y el círculo más pequeño  que encierra la unión  ∪ . En cada paso, prueba si el siguiente punto  para ser procesado está en ; si no, el algoritmo reemplaza el  por el resultado de una llamada recursiva del algoritmo en los conjuntos  y  ∪ . En función de si el círculo fue reemplazado o no,  se incluye en el conjunto . 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:
     input: Finite sets  and  of points in the plane
     output: Minimal disk enclosing  with  on the boundary, or undefined if no such disk exists
     if  is empty or || ≥ 3:
         if || = 1:
             (we do this to support multisets with duplicate points)
             (we assume that a circle with a radius of zero can exist)
              := [0]
             return circle(, 0)
         else if || = 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)
              := 
              := 
              := midpoint(, )
              := distance(, )
             return circle(,  / 2)
         else if the points of  are cocircular:
             return the ball they determine
         else:
             return undefined
 
     choose  in  (randomly and uniformly)
     D := welzl( - {  }, )
     if  is in :
         return 
     return welzl( - {  },  ∪ {  })

Otros algoritmos 
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 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 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. Ambos códigos Fortran y C están disponibles en .

 El problema de la esfera mínima se puede formular como un programa cuadrático 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. Hearn y Vijay 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: un algoritmo de Lawson se puede describir de esta manera como un algoritmo dual primario.

 Shamos y Hoey 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 
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.

Véase también 
 Esfera envolvente
 Circunferencia circunscrita
 Cadena más próxima

Referencias

Enlaces externos 
 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

Algoritmos
Círculos
Geometría computacional
Optimización combinatoria
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 . El problema del círculo mínimo fue propuesto inicialmente por el matemático inglés James Joseph Sylvester en En el plano es un ejemplo de un problema de localización de servicios ( el problema delcentro ) 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 . 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 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 determinar se 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 . Soluciones en tiempo lineal Como Nimrod Megiddo demostró , 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 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 reducir se a subexponencial , mientras que todavía se mantiene solo la dependencia lineal de N . El algoritmo de Welzl El algoritmo es recursivo y toma como argumentos dos conjuntos ( finitos ) de puntos y ; calcula el círculo delimitador más pequeño de la unión de y de , siempre que cada punto de 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 resolver se llamando al algoritmo con igual al conjunto de puntos que se van a encerrar y igual al conjunto vacío ; como el algoritmo se llama recursivamente , ampliará el conjunto mediante sucesivas llamadas recursivas hasta que incluya todos los puntos límite del círculo . El algoritmo procesa los puntos de en un orden aleatorio , manteniendo como lo hace el conjunto de puntos procesados y el círculo más pequeño que encierra la unión ∪ \ . En cada paso , prueba si el siguiente punto para ser procesado está en ; si no , el algoritmo reemplaza el por el resultado de una llamada recursiva del algoritmo en los conjuntos y ∪ \ . En función de si el círculo fue reemplazado o no , se incluye en el conjunto \ . 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 : input : Finite sets and of points in the plane output : Minimal disk enclosing with on the boundary , or undefined if no such disk exists if is empty or || ≥ if || = ( we do this to support multisets with duplicate points ) ( we assume that a circle with a radius of zero can exist ) \ := [ 0 ] return circle ( , else if || = ( 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 ) \ := \ := \ := midpoint ( , ) \ := distance ( , ) return circle ( , / else if the points of are cocircular : return the ball they determine else : return undefined choose in ( randomly and uniformly ) D \ := welzl ( - { } , ) if is in \ : return return welzl ( - { } , ∪ { } ) Otros algoritmos 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 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 implementar se para ejecutar se en el tiempo O ( nh ) . Elzinga y Hearn 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 . Ambos códigos Fortran y C están disponibles en \ . El problema de la esfera mínima se puede formular como un programa cuadrático 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 . Hearn y Vijay 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 : un algoritmo de Lawson se puede describir de esta manera como un algoritmo dual primario . Shamos y Hoey 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 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 recuperar se estableciendo todos los pesos en el mismo número . Al igual que con el problema no ponderado , el problema ponderado puede resolver se 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 . Vea se también Esfera envolvente Circunferencia circunscrita Cadena más próxima Referencias Enlaces externos 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 Algoritmos Círculos Geometría computacional Optimización combinatoria