Problema del círculo de radio mínimo

Question

Dado $n$ puntos en el plano 2D. Encuentre el radio mínimo del círculo que contiene al menos $k$ puntos ( $k\leq n$ )? Los puntos pueden estar dentro o en la circunferencia del círculo.

Intenté el enfoque de recursión; es decir, si $C(i)$ es el círculo con $i$ puntos sobre o dentro, pero no soy capaz de encontrar la relación entre $C(i)$ y $C(i1)$ . También lo he intentado seleccionando 3 puntos a la vez y luego encontrando el número de puntos que se encuentran dentro de él, pero da una complejidad de $O(n^4)$ . Así que necesito una solución optimizada.

Answer 1

Primer intento

Dejemos que las coordenadas de los puntos se denoten así: $(x_1,y_1),...,(x_n,y_n)$ .

Primero calcula el centro de "masa", $C$ :

$$\left(\frac1n\sum_1^n x_i,\frac1n\sum_1^n y_i\right).$$

A continuación, dibuje un círculo de radio $r$ centrado en $C$ . Cuenta los puntos que caen dentro del círculo real y aumenta o disminuye el radio para que el círculo contenga al menos $k$ puntos.

O, más bien, un algoritmo: calcular la distancia de los puntos de $C$ . Ordena estas distancias. Luego toma la $k^{th}$ distancia. Dibuja un círculo centrado en $C$ con ese radio.

EDITAR

Segundo intento Mi solución anterior no proporcionará el radio mínimo como se muestra a continuación:

Otro intento:

Tome el primer punto como centro y aumente el radio hasta que al menos $k$ los puntos caerán en el círculo. Luego toma el siguiente punto y haz lo mismo. Finalmente selecciona el mínimo de los radios que has obtenido.

Me temo que éste sigue sin ser el algoritmo óptimo.

Tercer intento

El algoritmo que da el radio óptimo es muy intensivo en computación: Tome todos los grupos de puntos de $k$ elementos. Hay $\binom nk$ tales grupos. Para cualquier grupo de este tipo utilice mi primer algoritmo. A continuación, seleccione el radio mínimo.