¿Encontrar el círculo más pequeño que encierra todos los puntos dadas sus coordenadas x, yx, yx, y?

Tengo un algoritmo que creo que calcula el radio mínimo de todos los puntos de la lista, que se ejecuta en O ( norte ) tiempo y es increíblemente fácil de implementar, pero ¿es correcto? Si es así, ¿se ha inventado antes? No se describe en Wikipedia .

El algoritmo, dada una lista de todos los puntos con X , y -coordenadas, es el siguiente:

  1. Obtener promedio de todos X y y coordenadas en la lista para obtener el centro del círculo ( 1 norte ( X 1 + X 2 + ⋯ + X norte ) , 1 norte ( y 1 + y 2 + ⋯ + y norte ) ) .
  2. Calcular la distancia entre todos los puntos desde el centro usando d ( ( X 1 , y 1 ) , ( X 2 , y 2 ) ) = ( X 2 − X 1 ) 2 + ( y 2 − y 1 ) 2 , para encontrar el punto con la distancia máxima desde el punto promedio. Entonces, esta distancia será el radio mínimo para cubrir todos los puntos.
Aclare su problema específico o proporcione detalles adicionales para resaltar exactamente lo que necesita. Tal como está escrito actualmente, es difícil decir exactamente lo que está preguntando.
El algoritmo que propuso suena similar al algoritmo descrito en esta pregunta .

Respuestas (1)

Su algoritmo es muy simple porque no siempre funciona.

Supongamos que nos dan los puntos ( 1 , 0 ) , ( 2 , 0 ) , y ( 6 , 0 ) . Su algoritmo primero los promediará para obtener el punto ( 3 , 0 ) , luego calcule una distancia máxima de 3 . Sin embargo, una mejor solución es tomar un círculo con centro ( 3.5 , 0 ) y radio 2.5 .

En general, si tiene un grupo de puntos juntos y un punto solitario lejos, el algoritmo propuesto dará un centro demasiado cerca del grupo.
Sin embargo, podría ser una forma interesante de minimizar el efecto de los valores atípicos sin la necesidad de discriminar qué puntos son atípicos.
@AIBreveleri: No. Si desea minimizar el efecto de los valores atípicos, debe eliminarlos antes de ejecutar el algoritmo que desee.
¿Encontrar el círculo más pequeño que encierra todos los puntos dadas sus coordenadas x, yx, yx, y?
RespuestasAquíPolítica de privacidad1y, 0v