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

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?

-
How effective/how exact a solution are you looking for? –  tomasz Jun 17 '12 at 16:23
–  leonbloy Jun 17 '12 at 17:58

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).
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.