Maximizing the number of points covered by a circular disk of fixed radius.

Question

Given a set of points in two dimensional space, and a radius r, what is the algorithm to find a disk of radius r that covers the maximum number of points?

Answer 1

A somewhat brute force solution (cubic complexity, I think):

1. The problem can be reduced to the problem of choosing a maximal subfamily of a family of disks of fixed radius $r$, such that its intersection is nonempty (a disk centered at any point in the intersection, with the same fixed radius $r$, will cover the centers of the subfamily).
2. Intersection of a family of disks of the same radius is either a single disk, or an area whose borders are arcs of the circles limiting the disks, so if the intersection of a family of at least two disks is nonempty, it contains an intersection of some two of the circles limiting the disks within its border (because border of intersection is contained within the union of the borders of the intersected sets, so the border will be several arcs (or a point, which can be seen as a degenerate arc); none of the arcs can be a full circle, and so each will be bounded by an intersection of some two of them).
3. We can find all the intersections between each pair of the circles analytically (by solving quadratic equations).
4. If there are none, the center of the disk we're looking for can be, for example, any of the points in question.
5. If there are some, we can directly check for each intersection of two circles how many of the special points are within $r$ of it, and then choose the best one as the center of the disk we're looking for.