5

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.

4
  • 1
    This is not really a programming question, would fit better on cs.stackexchange.com.
    – kebs
    Oct 15, 2014 at 15:37
  • You're going to have to brute force your way through this one. If, say, n==100 and k==3, you're just going to have to go through each combination of 3 points to find the one that has the smallest circle. You can quickly eliminate some combinations by checking if the distance between any two of the points is greater than the smallest diameter found so far.
    – Jonathan M
    Oct 15, 2014 at 15:37
  • 2
    This question appears to be off-topic because it is about algorithm design, not about implementation. It has been reposted on Computer Science where it is squarely on-topic. Oct 16, 2014 at 10:52
  • 1
    We've had this discussion on Meta many times. Questions like this are de facto on topic here. Oct 19, 2014 at 12:15

3 Answers 3

3

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.

1
  • 1
    If your points have integer or floating-point coordinates, the 2-approximation step is unnecessary since binary search works properly on integers and on floating-point numbers. If they don't and you're working with real numbers, you still only need to blow up n/k circles to get a 3- or 4-approximation.
    – tmyklebu
    Oct 16, 2014 at 4:09
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.

7
  • Yes, but unfortunately the time complexity is O(n^3) with n=10^4.
    – se0808
    Oct 15, 2014 at 15:56
  • It's not. Fix p1. There are n-1 points other than p1. Bolt a radius-r circle to p1 and spin it around; each point other than p1 will enter and leave the circle at most once per revolution.
    – tmyklebu
    Oct 15, 2014 at 16:10
  • Well, then O(iterations * n^2 log n) with O(n log n) from sort - but it seems to be too slow anyway.
    – se0808
    Oct 15, 2014 at 16:23
  • 1
    @tmyklebu If you were revolving a half-line bolted at p1 and sweeping through the points keep track of when points cross the angle sweep,I agree this is faster than O(n^2) per point p1. But you are revolving a circle of radius r, and figuring out when points enter and leave is non-trivial. I suggest more detail on how you will beat O(n^3), keeping in mind that the number of binary search steps is tied to numeric precision which could be arbitrary. Oct 15, 2014 at 16:23
  • user2566092: Fix r and p1. One can precalculate angles at which point enters and leave circle and sort them, then it will take linear time - as with revolving line.
    – se0808
    Oct 15, 2014 at 16:26
-2

One thought is that you could take the average of all of the points as the center, then grow the radius until you've covered k points. Under fairly uniform distributions this would probably do a pretty good job, but would fail for "clumpy" data. For example, if the points were in two tight clusters far from each other and k was small enough to just necessitate one of them, this would fail spectacularly. If there's the possibility for this clumping, consider using a clustering algorithm to identify local clusters, and then if one of them contains enough points use the algorithm just on that cluster.

4
  • 1
    This will not work. The center changes as you consider different sets of k points. See my comment to the OP above.
    – Jonathan M
    Oct 15, 2014 at 15:39
  • OP also said "approximately", which I take to mean finding an okay answer but not necessarily the optimal one.
    – MattPutnam
    Oct 15, 2014 at 15:42
  • 1
    @se0808, what do you mean by "approximately" in your original post? How approximate? Within 10% of the minimum? 50%?
    – Jonathan M
    Oct 15, 2014 at 15:43
  • @Johathan M, with a given precision - I meant something like binary search.
    – se0808
    Oct 15, 2014 at 15:49

Not the answer you're looking for? Browse other questions tagged or ask your own question.