Loading AI tools
Problema matemático de calcular el círculo más pequeño que contiene un conjunto de puntos dado en el plano euclidiano De Wikipedia, la enciclopedia libre
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.[2]
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.[3] 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.
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:
Demostración de que el disco de cobertura mínimo es único |
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 y . Sea r su radio compartido y sea la distancia entre sus centros. Entonces, 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 el centro y el radio , como se muestra en la siguiente imagen: Como r es mínimo, entonces , lo que significa que , por lo que los discos son idénticos.[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 , 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.[7]
El algoritmo es recursivo y toma como argumentos dos conjuntos (finitos) de puntos P y R; calcula el círculo delimitador más pequeño de la unión de P y de R, siempre que cada punto de R 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 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. Se puede demostrar que el tiempo total es lineal.
algorithm welzl:[8] input: Finite sets P and R of points in the plane output: Minimal disk enclosing P with R on the boundary, or undefined if no such disk exists if P is empty or |R| ≥ 3: if |R| = 1: (we do this to support multisets with duplicate points) (we assume that a circle with a radius of zero can exist) p := R[0] return circle(p, 0) else if |R| = 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) p0 := R[0] p1 := R[1] center := midpoint(p0, p1) diameter := distance(p0, p1) return circle(center, diameter / 2) else if the points of R are cocircular: return the ball they determine else: return undefined choose p in P (randomly and uniformly) D := welzl(P - { p }, R) if p is in D: return D return welzl(P - { p }, R ∪ { p })
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.[14][18][19]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.