Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
How effective/how exact a solution are you looking for? –  tomasz Jun 17 '12 at 16:23
1  

1 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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.