Given $n$ points in 2D plane .Find the minimum radius of the circle which contains at least $k$ points ($k\leq n$)? The points can be in or on the circumference of the circle.
I tried the recursion approach; i.e, if $C(i)$ is the circle with $i$ points on or inside,but I am not able to find the relation between $C(i)$ and $C(i−1)$. Also I tried it by selecting 3 points at a time and then finding the no. of points lying within it , but it gives a complexity of $O(n^4)$. So I need an optimised solution.
First attempt
Let the coordinates of the points be denoted like this: $(x_1,y_1),...,(x_n,y_n)$.
First calculate the center of "mass", $C$:
$$\left(\frac1n\sum_1^n x_i,\frac1n\sum_1^n y_i\right).$$
Then draw a circle of radius $r$ centered at $C$. Count the points falling inside the actual circle and increase or decrease the radius so the circle contains at least $k$ points.
Or, more like an algorithm: calculate the distance of the points from $C$. Order these distances. Then take the $k^{th}$ distance. Draw a circle centered at $C$ with that radius.
EDIT
Second attempt My solution above will not provide the minimum radius as shown below:
Another try:
Take the first point as a center and increase the radius until at least $k$ points will fall in the circle. Then take the next point and do the same. Finaly select the minimum of the radii you got.
I am afraid that this is still not the optimal algorithm.
Third attempt
The algorithm giving the optimal radius is very computing intensive: Take all the groups of points of $k$ elements. There are $\binom nk$ such groups. For any such group use my first algorithm. Then select the minimum radius.