Naive Algorithm

For an arbitrary pair of points in the given set (say A and B), construct the circles with radius ‘R’ that touches both the points. There are maximum 2 such possible circles. As we can see here maximum possible circles is for CASE 1 i.e. 2.

• For each of the constructed circle, check for each point in the set if it lies inside the circle or not.
• The circle with maximum number of points enclosed is returned.

Time Complexity: There are ⁿC₂ pair of points corresponding to which we can have 2ⁿC₂ circles at maximum. For each circle, (n-2) points have to be checked. This makes the naive algorithm O(n³).

Given ‘n’ points on the 2-D plane, find the maximum number of points that can be enclosed by a fixed-radius circle of radius ‘R’. 
Note: The point is considered to be inside the circle even when it lies on the circumference.

Examples: 

Input: R = 1
points[] = {(6.47634, 7.69628), (5.16828 4.79915),
(6.69533 6.20378)}
Output: 2
The maximum number of points is 2

Input: R = 1
points[] = {(6.65128, 5.47490), (6.42743, 6.26189)
(6.35864, 4.61611), (6.59020 4.54228), (4.43967 5.70059)
(4.38226, 5.70536), (5.50755 6.18163), (7.41971 6.13668)
(6.71936, 3.04496), (5.61832, 4.23857), (5.99424, 4.29328)
(5.60961, 4.32998), (6.82242, 5.79683), (5.44693, 3.82724) |
(6.70906, 3.65736), (7.89087, 5.68000), (6.23300, 4.59530)
(5.92401, 4.92329), (6.24168, 3.81389), (6.22671, 3.62210)}
Output: 11
The maximum number of points is 11