Finding the position of a given circle that contains the most randomly placed points

Question

Given are a random number of points, randomly scattered in a finite plane, and a circle of a given size.

How do I know where to position the circle so that the most points possible are inside the circle?

Answer 1

We may assume wlog that at least one point is on the circle boundary, for otherwise we can translate the circle until one of th einterior points is about to leave it. The only exception is when the maximal number is $0$, i.e., there are no points to begin with.

In fact, we can usually assume wlog that there are two points on the boundary, for otherwise we can rotate around the one point on the boundary that we already have from the preceeding paragraph, until another point is about to leave the interior. As above, the only exception to this is when it is impossible to cover two points to begin with.

This suggests the following algorithm: Loop over all ${n\choose 2}$ pairs of points. If their distance is $\le $ the circle diameter, check which other points are inside the two possible circles with the given chord. All in all, this is an $O(n^3)$ algorithm. I am confident that this can be sped up by first determining a Delaunay triangulation and use that to reduce the number of chords to be tested.