# Select circle with given radius that contains most points

Given some points on a coordinate system and some radius r, I need to place a circle with radius r somewhere on the coordinate system such that that circle includes the most points.

I tried solving it by taking each pair of points and if it is possible, generate the two circles that pass trough those two points and have radius r.

Here I found 2 possible circles that have points a and b on their perimeter with radius 2. One circle contains most points so that would be the solution of this problem.

However, I am not sure that this works. One easy counter example is when we have only one point. No pairs can be generated so no circles can be generated. In my code, I just added a circle for every point in addition to my circle generating nonsense from before. But that also fails to give me the correct result.

How do I really go about solving this?

• This is a well-studied problem in computational geometry. You may for instance start reading the paper by Mark de Berg, Sergio Cabello, Sariel Har-Peled: "Covering Many or Few Points with Unit Disks", Theory Comput. Syst. 45(3): 446-469 (2009), and follow some of the references there. – Gamow Jan 27 '19 at 20:14
• @Gamow that reference focuses on the harder problem of using $m$ circles to cover the max number of points, and mentions that $m=1$ is solvable in $O(n^2)$ time, as D.W.'s solution points out the OP's solution is. – JimN Feb 27 '19 at 4:14

There may be other algorithms that are even faster, but your algorithm shows that the problem can be solved in $$O(n^2)$$ time.