largest circle which encloses no more than 11 points [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

A math problem I've been stuck on for a couple days.

Given a set of points on a 2D plane (more than 11), find the largest circle possible which will not enclose more than 11 points.

The obvious approach would be to take all possible subsets of size 12, then find the minimum enclosing circle for each, but that would take far too long to calculate.

any ideas on a more efficient method?

Answer 1

I suspect that there's a thoroughly impractical O(n log n)-time algorithm that computes the order-12 (!) Voronoi diagram and proceeds as in the O(n log n)-time algorithm for largest empty circle. Realistically, every viable circle is determined by three of the input points (on the boundary) or two (as the diameter). Naively trying all of them is quartic time, but for each pair of points P and Q, the points on one side of the line PQ are totally ordered with respect to which other points above the circle encloses, as are the points below. This insight gets us to n^3 log n, by sorting; quadratic should be possible using a selection algorithm.

Answer 2

For each point:

• Compute the distance to every other point - O(n)
• Run a selection algorithm to find the 12th closest point - O(n).
  Let x = the distance between these two points.

Find the minimum x. Subtract the smallest possible value from that value, then you have your circle diameter.

Running time: O(n²).