You are given N points on 2-D plane. How can I find out minimal radius of a circle which contains at least M of these points?

algorithm for code

I searched for smallest enclosing circle problem but that was not for at least m?



Sariel Har-Peled and Soham Mazumdar (2005), "Fast algorithms for computing the smallest $k$-enclosing circle", Algorithmica 41 (3): 147–157, doi:10.1007/s00453-004-1123-0.


This is a N algorithm

  1. Given a set of N points P, draw a line that have at least M points at one side of it.
  2. Name this subspace with at least M points as S
  3. Pick a point that lays in S and call it center
  4. Calculate the most distant point from center and call the distance as ray.

There you go, you have circle with a center and a ray.

Obs. the way you chose the center is what determinates the size of your circle

  • $\begingroup$ Why the negative vote? $\endgroup$ – Henrique Almeida Marcomini Jan 18 '17 at 10:38
  • 3
    $\begingroup$ There is no reason why this algorithm gives the circle with the smallest radius. $\endgroup$ – Sasho Nikolov Jan 18 '17 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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