Minimal covering circle [closed]

Question

There are n points on the plane, how can one approximately find the minimal radius of a circle that covers some k out of n these points? Number n is supposed to be less then 10^4.

There is lots of information on the case k==n in Wikipedia, but I found nothing on general case.

Answer 1

Here's an algorithm that, given a radius r > 0 and an approximation constant c > 0, either returns a circle of radius (1+c) r enclosing at least k points or declares that there is no circle of radius r strictly enclosing at least k points. The running time is O(n (1 + k^-1 c^-2 log c^-1)), which, when used in conjunction with binary search to obtain a sufficiently coarse estimate, should be faster than tmyklebu's algorithm. (To initialize the search, it's possible in time O(n^2) to get a 2-approximation for r by looping over the points and running quickselect to find the kth closest other point.)

Partition the points by placing point (x, y) in a square bin labeled (floor(x/(2r)), floor(y/(2r))). Every circle of radius r has an interior that overlaps at most four bins. If there exists a circle of radius r enclosing at least k points, then there exist i, j such that the bins (i, j), (i, j+1), (i+1, j), (i+1, j+1) together hold at least k points.

For each of these subproblems, place each involved point (x, y) in a smaller square bin, (floor(x/w), floor(y/w)), where w = cr/(3sqrt(1/2)) is a sufficiently small width. Now prepare an O(c^-1) by O(c^-1) matrix where each entry tells how many points are contained in the corresponding bin. Convolve this matrix in two dimensions with a zero-one matrix indicating the bins completely contained in a radius-(1+c)r circle. The latter matrix might look like

01110
11111
11111
11111
01110.

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

Answer 2

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

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