Find the most points enclosed in a fixed size circle

Question

This came up when a friend talked about a programming competition, and we wondered what the best approach was:

Given a list of points, find the centre of a circle of predetermined size that covers the most points. If there are several such circles, its only important to find one of them.

Example input: 1000 points, in a 500x500 space, and a circle of 60 diameter.

Answer 1

Unless I've missed something obvious I think there is a simple answer.

For a rectangular area MxN, number of points P, radius R:

• Initialise a map (e.g. 2D array of int) of your MxN area to all zeroes
• For each of your P points
  • increment all map points within radius R by 1
• Find map element with maximum value - this will be the centre of the circle you are looking for

This is O(P), assuming P is the variable of interest.