Algorithm to cover maximal number of points with one circle of given radius

Question

Let's imagine we have a plane with some points on it. We also have a circle of given radius.

I need an algorithm that determines such position of the circle that it covers maximal possible amount of points.
If there are many such positions, the algorithm should return one of them.
Precision is not important and algorithm may do small mistakes.

Here is an example picture:

Input:
int n (n<=50) - number of points;
float x[n] and float y[n] - arrays with points' X and Y coordinates;
float r - radius of the circle.

Output:
float cx and float cy - coordinates of the circle's center

Lightning speed of the algorithm is not required, but it shouldn't be too slow (because I know a few slow solutions for this situation)

C++ code is preferred, but not obligatory.

Thank you...

Answer 1

This is famous K-closest point algorithm. Described here: http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf

Answer 2

Edited to better wording, as suggested :

Basic observations :

• I assume the radius is one, since it doesn't change anything.
• given any two points, there exists at most two unit circles on which they lie.
• given a solution circle to your problem, you can move it until it contains two points of your set while keeping the same number of points of your set inside it.

The algorithm is then:

• For each pair of points, if their distance is < 2, compute the two unit circles C1 and C2 that pass through them.
• Compute the number of points of your set inside C1 and C2
• Take the max.

Answer 3

The problem reverts back to finding the global optimum of a function f :R x R -> N. The input for f is the center point of the circle, and the value, of course, is the number of included points from the set. The graph of the function will be discontinuous, staircase-like.

You could start by testing the function in each point corresponding to a point in the set, order the points by decreasing values of f, then intensify search around those points (for example moving out along a spiral).

Another option is to consider all intersection points of segments connecting any pairs of points in the set. Your optimal point will be at one of these intersections I think, but their number is probably too big to consider.

You may also hybridise options 1 and 2, and consider intersections of the segments generated from points around 'good set points'.

Anyhow, unless the number of set points is low (allowing you to check all intersections), I don't think you can guarantee to find the optimum (just a good solution).

Answer 4

If it is true that precision is not important and algorithm may do small mistakes then I think the following.

Let f(x,y) is a function which has a maximum at the point (0,0) and is only significant at the points inside of circle of radius R. For example, f(x,y) = e^{(x^2 + y^2)/ (2 * R^2)}.

Let (x_i,y_i) are points and E_i(x,y) = f(x - x_i, y - y_i).

Your problem is to find the maximum of \sum_i E_i(x,y) .

You can use a gradient descent starting it from each point.

Answer 5

At a first glance, I would say a quad tree solution.

Also, there is an information visualization/Data mining method called K-means which makes clusters of given data. It can be used with added functionality in the end to fit your purpose.

The basic algorithm for K-Means is:

1. Place K points into the space represented by the items that are being clustered - These points represent initial group centroids
2. Assign each data item to the group that has the closest centroid
3. When all items have been assigned, recalculate the positions of the K centroids by calculating the mean position of your dots
4. Repeat Steps 2 and 3 until the centroids no longer move, or move very little

The added functionality would then be:

1. Calculate number of points within your circle positioned at the K centroids
2. Choose the one that suits you the best ;)

Sources: K-means algorithm: http://servus.itn.liu.se/courses/TNM048/Slides2009/InfVizTNM048%202009%20Lecture%204%20Large%20data.pdf - Linköping University

Quadtree: en.wikipedia.org/wiki/Quadtree

A quick search on wikipedia and you find source code: en.wikipedia.org/wiki/K-means_clustering

(sorry but i cant use more than one hyperlink in my post heheh...

Answer 6

This is the "disk partial covering problem" in the literature -- that should give you a good place to start googling. Here's a paper covering one possible solution, but it is a little intense mathematically: http://www.utdallas.edu/~edsha/papers/bin/ISPAN04_cover.pdf

As a matter of fact, this falls in the area called computational geometry, which is fascinating but can be hard to get a toehold in. There's a good overview by deBerg on various algorithms related to the subject.

Answer 7

If you want something simple, take random position (x,y), calculate number of points inside circle and compare with previous position. Take the maximum. Repeat the operation any times you want.

Why the hell downvote? Ever heard about Monte Carlo methods? Actually for a huge amount of points, deterministic algorithm may not finish in reasonable time.

Answer 8

Might I suggest a density map? Find the min and max bounds for the x and y. Divide the range of the x and y bounds into bins having widths equal to the diameter of your circle. Count the number of points in each bin for the x and y separately. Now find the intersection on your density map between the highest ranked x bin with the highest ranked y bin.

This is a VERY fast algorithm to quickly generalize large data sets but it is not always accurate, to improve accuracy you can slice the bins into smaller and smaller pieces or shift the bin positions to the left or right n times and use a voting system to select the answer that occurs most often between trials.

Answer 9

You could pixelize the whole area, then go to each point and increase the value of all pixels within the circle of the radius around that point. The pixels with the highest sum are good candidates.

Of course, you might lose some good areas or "hallucinate" good areas due to rounding errors. Perhaps you could try to do a rough pixellation first, then refine the promising areas.