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 circundante más pequeño ) es un problema matemático de 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 , es 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 avión es un ejemplo de un problema de ubicación de una instalación (el problema de un centro ) en el que se debe elegir la ubicación de una nueva instalación para brindar servicio a varios clientes, minimizando la distancia más lejana que cualquier cliente. debe viajar 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 limitada se pueden resolver en el peor de los casos en tiempo lineal .
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 cualquier conjunto de puntos en el plano y suponga que hay dos discos envolventes de P más pequeños , con centros en y . Sea su radio compartido y sea la distancia entre sus centros. 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 centro y radio , como se muestra en la siguiente imagen:
Dado que r es mínimo, debemos tener , es decir , que los discos sean idénticos. [4]
