chill21's blog

Minimum radius of the circle to cover atleast m points ?
By chill21, history, 10 years ago, In English

Given N points in the 2- D plane , find minimum radius of the circle which encloses atleast m points?

thanks in advance

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

What is an algorithm for enclosing the maximum number of points in a 2-D plane with a fixed-radius circle? This can be solved in n*n*logn (see here)

Now to solve your problem all you need to do is to binary search over possible range of R to find the minimum R which encloses at least m points.

This problem was asked in recent codechef long challenge (click)

→ Reply