Minimum cover circle

Question

There are n points on the plane, how can one approximately find the minimum radius of a circle that covers some k of n of these points? The number n must be less than 10 ^ 4.

a lot of information on the case k == n on Wikipedia, but I did not find anything in the general case.

Answer 1

Here, an algorithm that, given the radius r > 0 and the approximation constant c > 0 , returns a circle of radius (1+c) r covering at least k points, or announces that there is no circle of radius r strictly covering at least k points. The running time is O(n (1 + k^-1 c^-2 log c^-1)) , which when used in conjunction with a binary search to get a fairly rough estimate should be faster than the tmyklebu algorithm. (To initialize the search, it is possible, during O(n^2) to obtain a 2 approximation for r by cycling through the points and run quickselect to find k th the nearest other point.)

Separate the points by placing the point (x, y) in a square cell labeled (floor(x/(2r)), floor(y/(2r))) . Each circle of radius r has an inner part that overlaps no more than four boxes. If there exists a circle of radius r spanning at least k points, then there exist i, j such that bins (i, j), (i, j+1), (i+1, j), (i+1, j+1) together have at least k points.

For each of these subtasks, place each participating point (x, y) in the cell of the smaller square, (floor(x/w), floor(y/w)) , where w = cr/(3sqrt(1/2)) is enough small width. Now prepare the matrix O(c^-1) by O(c^-1) , where each entry indicates how many points are contained in the corresponding bin. Collapse this matrix in two dimensions with a zero matrix denoting cells that are completely contained in a circle of radius (1+c)r . The last matrix may look like

 01110 11111 11111 11111 01110. 

Now we know for each center of the grid a number that is limited by how many points a circle of radius r will contain and limited by how many points a circle of radius (1+c) r will contain.

Answer 2

Given the radius of the candidate r , you can find the maximum number of points that can be contained in a circle of radius r by taking each pair (p1, p2) points and seeing how many points are contained in each of two circles of radius r with p1 and p2 at the border.

Knowing this, you can perform a binary search for the smallest r , so some circle of radius r contains k or more points.

Answer 3

One thought is that you can take the average of all the points in the center, and then increase the radius until you reach k points. With fairly uniform distributions, this would probably do a good job, but would not work for the “lumpy” data. For example, if the points were in two dense clusters, far from each other, and k was small enough to just require one of them, this would not be impressive. If there is a possibility for this combination, consider using the clustering algorithm to determine local clusters, and then, if one of them contains a sufficient number of points, use the algorithm for this particular cluster.