Algorithm to cover maximal number of points with one circle of given radius

Question

we have a plane with some points on it. We know coordinate of each point apriori. We also have a circle of unit radius.

I need an algorithm that determines optimal/sub-optimal position of a circle that covers maximal number of points. Precision is not important and the algorithm may do small mistakes. I'm mostly looking for an algorithm whose complexity is low. (O(n) would be great).

Answer 1

I found the answer here. The algorithm has $O(n^2 logn)$ complexity

https://www.quora.com/What-is-an-algorithm-for-enclosing-the-maximum-number-of-points-in-a-2-D-plane-with-a-fixed-radius-circle

Answer 2

You're looking for the algorithm that solves both The Texas Sharpshooter Problem and The Bomb Problem. See the link for code. Basically, find the triangle with smallest circumradius, then work up.