Welcome to NRICH.

 
Spotting clusters of randomly placed points on a grid
By Tom Hardcastle (P2477) on Wednesday, July 26, 2000 - 06:42 pm:

Suppose I have a large number of randomly placed points on a large grid, where I know the co-ordinates of all the points. I want to place a disc of radius r onto the grid such that it covers the maximum number of points.
Any suggestions for efficiently determining where the centre of the disc should be?

By Dan Goodman (Dfmg2) on Saturday, July 29, 2000 - 04:07 am:

OK, I have a solution, but it is very inefficient, for those familiar with big-O notation, the algorithm takes O(n3) steps to compute (where n is the number of points), simply put this means that it takes less than kn3 operations for some constant k. O(n3) is usually considered pretty inefficient for an algorithm.

The key thing to note for my algorithm, is that if you have a best placed circle which encompasses at least two points, then there is another best placed circle encompassing the same number of points which has two points on the boundary. You can see this geometrically, by slowly moving the best placed circle to the right until one of the points touches the edge, then rotating the circle about the point touching the edge until another point touches the edge. Therefore, there is a best circle which has the property that there are two points on the boundary of the circle. This suggests a simple algorithm. For all pairs of points not more than a distance of 2r away from one another, calculate the centres of the (at most) two circles which have those points on the boundary. This can be done with some elementary vector algebra, which I can be more explicit about if you want. Then, compute the number of points inside both of these circles. Do this for all of the pairings, and choose the one with the most points inside it.

I think that this method guarantees the best choice of a circle assuming that the centre of the circle doesn't have to be on a grid point. There are some simple optimizations for this algorithm, you might even be able to reduce the computational complexity below O(n3), although nothing immediately occurs to me.

By Tom Hardcastle (P2477) on Saturday, August 5, 2000 - 09:28 pm:

The center of the circle is on a grid point, which makes a solution involving checking every grid point possible but inefficient. Sorry for not mentioning this before. Also, perfect answers are not required, just a strategy, although perfect answers would be nice.

Tom

By Dan Goodman (Dfmg2) on Monday, August 7, 2000 - 06:18 am:

By the way, what do you need this algorithm for? I've come up with a couple of plausible uses for such an algorithm (e.g. placing radio masts to deliver a signal to the maximum number of homes), but what's yours, if that's not too personal a question? :) I haven't yet managed to come up with an efficient strategy, but I'll keep thinking about it.

By Tom Hardcastle (P2477) on Tuesday, August 8, 2000 - 02:21 am:

It's an attempt to allow a computer to spot important areas on a grid; basically, there is a cost for each circle that is placed on the region and every object within that circle is affected somehow. The aim is to maximise the effect/cost ratio. This is important in e.g. strategy games, but also more generally.

I do have a partial solution for the strategy game concept where efficiency becomes important because at each 'event' time within the game there will only be small changes. So if each point on the grid is labelled with the number of objects within a circle centred on that point, these labels can be updated on the fly with a longer initial set up. It's not a very pretty way of doing it, though

Tom