So given n points on a plane, I'm trying to find a pair of concentric circles so that all the points are between the circles, and that area is as small as possible, in linear time. What I'm thinking is to use Welzl's algorithm to find the smallest enclosing circle, then iterate through the points to find the smallest distance to the center of the circle. I just don't know if this even is correct or guarantees an optimal solution. Is this the right way to approach this and can it be solved this way? Also - is this the same problem as the roundness problem?

  • $\begingroup$ hmm a variation of welzl's algorithm to find both circles is doable (in fact since they must share a common center, it might be easier).. $\endgroup$
    – Nikos M.
    Commented Jul 10 at 18:47
  • $\begingroup$ I suggest you try implementing your idea, implementing a slow reference implementation that is known to be correct, and testing it on many randomly chosen problem instances to see if the two implementations always give the same answer. That would be a good first step to gain confidence in whether the approach might plausibly be good. $\endgroup$
    – D.W.
    Commented Jul 10 at 19:41
  • 3
    $\begingroup$ @D.W. That won't be necessary, it's easy to show the proposed algorithm can be arbitrarily bad, not even approximating the optimal solution in ratio. Consider three points lying on a section of a circle. Then the optimal solution can have area that is arbitrarily small, whereas the smallest-enclosing-circle solution has nontrivial area: i.imgur.com/bLQEebJ.png. $\endgroup$
    – orlp
    Commented Jul 11 at 11:35
  • $\begingroup$ @orlp - it'd be nice to see a counterexample, where the center is inside the point set convex hull $\endgroup$
    – HEKTO
    Commented Jul 11 at 19:56
  • 2
    $\begingroup$ doc.cgal.org/latest/Bounding_volumes/… $\endgroup$
    – HEKTO
    Commented Jul 11 at 20:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.