1

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.

Hagen von Eitzen
  • 374,180
JonathanReez
  • 119

2 Answers2

3

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.

OR.
  • 5,941
  • Thanks. But how could you prove that there always exists a line separting a certain number of points on one side? – JonathanReez Jul 21 '13 at 13:57
  • There are only finitely many lines in only fninitely many directions passing to two (or more) points. Shifting a line of any other direction will separate the points as desired. All we need is that the $n$ points are distinct. – Hagen von Eitzen Jul 21 '13 at 14:10
2

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$:

enter image description here

Martin Thoma
  • 9,821