Greetings, all. Here's my situation: I have a set of points bounded by a circle of radius r. My goal is to identify within this circle a region bounded by another circle of of radius 0.5r that contains the greatest number of points -- with an understanding that there might be multiple circles that would enclose the same number of points. From some of the Google searches I've tried thus far, this seems to be a type of "cluster analysis" problem. I invite any input on how best to achieve the goal.

For every pair of points in the set that are not farther than r apart, look at the two circles of radius 0.5*r that pass through those two points. Pick the circle that contains the most points among all those. The algorithm is O(n^3). If n is not too big, you could just do that.

That's an approach I had not considered. The number of points is small enough to make the approach feasible, but the method described allows for the smaller circle to lie partially outside the larger circle. I apologize for not mentioning this constraint initially, but I want to ensure that the smaller circle lies completely within the larger circle, allowing for the possibility of the circles touching at one point.

As a speed optimization, you could always pre-process the points into a grid so that when you count how many points are in a circle you only consider the points in the grid squares which the circle touches at all.

Also if a circle completely contains a grid square you can then just add the count of points inside the grid without having to test each point against the circle (:

The number of points to be evaluated will be so small (probably no more than 15 or so) that a grid optimization might not offer much benefit. Still, it's a handy tip.

Quote:Original post by alvaro
For every pair of points in the set that are not farther than r apart, look at the two circles of radius 0.5*r that pass through those two points. Pick the circle that contains the most points among all those.

Are you sure that optimal solution will contain two points on the edge?

Quote:but I want to ensure that the smaller circle lies completely within the larger circle,

When you have two points, you can check if the circle they define lies within the outer circle.

I'm after a "good enough" solution -- meaning that I want the inner circle containing a maximum number of points (recognizing that there may be more than one), but it doesn't need to be a minimum bounding circle around the points.

I'll try the brute force approach using alvaro's proposed algorithm and add a check whether the center of the larger circle is bounded by the smaller circles. This seems like a straightforward way to ensure that the smaller circle lies within the larger circle. Thanks, alvaro, for the algorithm and thanks to all other contributors. I'll keep monitoring the thread in case anyone else cares to pitch an alternative idea.

In the problem as I originally understood it, I am certain that an optimal circle exists that contains two on its border. Just consider any optimal circle and move it a little bit, until one of the points inside touches the border. Then pivot around that point until another point touches the border. No points have gone in or out of the circle as I moved it, so the new circle is also optimal, and it contains two points in its border. So it is safe to just search among circles with that property.

With the additional constraint of the smaller circle being contained int the larger one, I think it should be enough to check circles that contain two points and are contained in the larger circle, plus circles that contain one point and are tangent to the large circle. I think a similar argument to the one above justifies this, but it's really late and I might not be thinking straight. I'll think about it some more tomorrow.

This is a very nice problem and alvaro is right.

You start off with an optimal circle. Since the bounding circle is of radius r and the optimal circle is of radius 0.5r, you can always move the optimal circle around inside the bounding circle until you touch one other point*. If you touch several points, pick a random one. Rotate the circle around that point until you a) touch another point or b) touch the bounding circle. The circle you end up with either touches 2 points or 1 point and the bounding circle. It is still optimal since no point left the circle.

Hence, the algorithm works as follows:
1) For every pair of points A and B closer than r, check the two circles through A and B. Ignore circles not inside the bounding circle.
2) For every point whose distance to the bounding circle is smaller than 0.5*r, check the two circles through that point tangent to the bounding circle.
Still O(n^3). Part 2) is even O(n^2).

*To see this, imagine the diameter through the centers of the two circles. Move the optimal circle along this diameter all the way to one side until it touches the bounding circle, then all the way to the other side until it touches the other side of the bounding circle. Since the radius of the circle you moved is 0.5*r and the radius of the bounding circle is r, the two extreme circles don't overlap - their intersection is empty. But since there was at least one point in the optimal circle, you must have "lost" at least one point while moving the optimal circle around.