Being given a radius $R$ and $N$ points on a $x-y$ plane , I want to draw a circle with radius $R$ such that it maximizes the number of points enclosed.
My Approach:
If there a circle C that encloses $M$ points, then by slightly moving C it will touch at least two points.
So, essentially we just need to check all circles which touch (at least) 2 points:
- For each pair of points in the given set, construct a circle with radius R that touches both points. For each point pair there are at most two such circles.
- For each constructed circle, check for if each given point if it is
inside it. Return the circle that encloses the maximum number of
points.
Time Complexity $O(N^3)$
Is there an algorithm that can reduce my time complexity ?