Building a circle containing a specific number of points on a plane

Question

Given a 2-dimensional plane containing $n$ random points, prove that it's always possible to build a circle containing exactly $k$ points; where $n\gg k$.

A friend told me this problem and the solution a few months ago, but I completely forgot it. I also couldn't find a solution to the problem on the Internet, so I wanted to ask the question here.

Answer 1

You can construct a solution like this:

Let Points be your n random points
foreach i in 1..(n-1):
    foreach j in (i+1)..n:
        construct the line L_{i,j} which has equal 
        distance to Points[i] and Points[j]
choose a random point c that is not on any of the constructed lines 
this point is your center

You can guarantee for $c$ that for every circle around it, you will not have two points on the line. Why? Because if you had two points on the circle line, they would have the same distance in $c$ which means they would be on one line $L_{i,j}$. The same argumentation works for more than two points.

There are points left, because you've just drawn a finite number of lines which can't cover a plane.

As you can increase the size of the circle in steps, where you $r_t$ is the radius to the $t$-th next point, you will only have $t$ points in your circle.

Additional information

I don't know how a line of points that have equal distance to two Points $A, B$ is called in English (in German, it is "Mittelsenkrechte"). Here is an image of what I mean. The blue line is the "Mittelsenkrechte" for $A$ and $B$:

Answer 2

Apply inversion with center on the circle (the circle can be assumed to pass through some point you choose). The circle you are looking for will become a line. Then it is easy to move the line so that a certain number of points are on one side. Invert back and you get the circle.