Introduction

Finding the maximum number of points that fit inside a circle of fixed radius is a classic computational-geometry problem. The useful insight is that an optimal circle can be positioned so that at least one or two input points lie on its boundary, which turns an infinite search space into a finite algorithm.

Key Geometric Idea

If a circle of radius r encloses the best possible set of points, you do not need to test every center in the plane. For an optimal solution, you can focus on circles whose boundary passes through one point or through two points.

Why two points matter:

• If two points are farther apart than 2r, no circle of radius r can contain both on its boundary.
• If two points are within distance 2r, there are up to two circle centers of radius r that pass through both points.

So a practical exact algorithm is:

1. For each point pair within distance 2r, compute candidate circle centers.
2. Count how many points lie inside each candidate circle.
3. Track the maximum count.

This is not the most asymptotically optimal approach, but it is clear and works well for many input sizes.

Computing Candidate Centers

Suppose the points are p1 and p2. Their midpoint gives a baseline, and the candidate centers lie on the perpendicular bisector at a distance determined by the radius.

Here is a complete Python implementation:

1import math
2
3def points_in_circle(points, radius):
4    if not points:
5        return 0
6
7    def count_points(cx, cy):
8        r2 = radius * radius + 1e-9
9        return sum(
10            1
11            for x, y in points
12            if (x - cx) ** 2 + (y - cy) ** 2 <= r2
13        )
14
15    best = 1
16
17    for i in range(len(points)):
18        x1, y1 = points[i]
19
20        # A circle centered on the point itself is a valid baseline candidate.
21        best = max(best, count_points(x1, y1))
22
23        for j in range(i + 1, len(points)):
24            x2, y2 = points[j]
25            dx = x2 - x1
26            dy = y2 - y1
27            d = math.hypot(dx, dy)
28
29            if d > 2 * radius or d == 0:
30                continue
31
32            mx = (x1 + x2) / 2.0
33            my = (y1 + y2) / 2.0
34
35            h = math.sqrt(radius * radius - (d / 2.0) ** 2)
36            ux = -dy / d
37            uy = dx / d
38
39            centers = [
40                (mx + h * ux, my + h * uy),
41                (mx - h * ux, my - h * uy),
42            ]
43
44            for cx, cy in centers:
45                best = max(best, count_points(cx, cy))
46
47    return best
48
49
50pts = [(0, 0), (1, 0), (0, 1), (2, 0), (2, 2)]
51print(points_in_circle(pts, radius=1.5))

The helper count_points checks how many input points fall inside or on the circle boundary.

Complexity

This implementation examines all point pairs and, for each candidate center, scans all points to count membership. That gives roughly O(n^3) time in the straightforward form.

For moderate input sizes, this is often acceptable and much easier to implement correctly than more advanced angular sweep algorithms. If n becomes very large, then specialized O(n^2 log n) methods or spatial indexing become more attractive.

Precision Matters

Geometry code is sensitive to floating-point noise. In the example above, the containment test uses a tiny epsilon:

r2 = radius * radius + 1e-9

Without that tolerance, points that are mathematically on the boundary can be excluded because of rounding error.

That matters especially when:

• many points lie near the circle edge
• coordinates are large
• the input comes from previous floating-point computation

When a Simpler Approximation Is Enough

If you are doing visualization, rough clustering, or an interactive UI tool, you may not need an exact optimum. A grid search over candidate centers can be simpler to code, though less precise.

For interview problems or algorithmic correctness, however, the pair-of-points construction is the more defensible exact method.

Common Pitfalls

The biggest mistake is checking only circles centered on the existing points. The optimal circle center usually lies somewhere between points, not necessarily on one of them.

Another issue is forgetting that a pair of points farther apart than 2r cannot lie on the same circle of radius r. Skipping that check leads to invalid square roots and broken geometry.

Developers also underestimate floating-point error. Without a small epsilon, boundary cases can fail unexpectedly.

Finally, brute-forcing every possible center on a continuous plane is conceptually wrong. The whole problem becomes tractable only after reducing the candidate set using geometry.

Summary

• An optimal fixed-radius circle can be found by testing centers derived from point pairs.
• Only pairs within distance 2r can define a valid circle of radius r.
• For each valid pair, there are up to two candidate centers.
• A straightforward exact implementation is about O(n^3) and is often practical for moderate inputs.
• Use a small epsilon in boundary checks to avoid floating-point surprises.