Visualisation of problem

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. Kinda like this

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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Gamow Jan 27 '19 at 20:14
  • $\begingroup$ @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. $\endgroup$ – JimN Feb 27 '19 at 4:14

Your algorithm is correct. If the best circle contains one point, your post-processing step will find it. If the best circle contains two or more points, then there is a way to shift it around so it contains the same set of points and also two of them are on the perimeter; thus, in this case your algorithm will also find it.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.