How to find the minimum radius circle that encloses all the given points?

Question

Suppose I have some 1000 odd points on a plane.

Then, what I think could be done is to discard the points that do not affect the radius of the circle in any way - the points through which the convex hull does not pass [using one of the several algorithms]. This leaves us with points that do matter.

Now from here on, what can be done to find that minimum radius circle?

I am looking to generalize this for ellipses once I understand how it can be done for circles.

Any link to some "public source code" would be helpful, so that I can modify it for ellipses.

Answer 1

One option is the CGAL Computational Geometry Algorithms Library. It is open source, but it is also large - the biggest problem you'll have, I suspect, is finding the needle in the haystack.

Of course (and this is partly in apology to Martin), you can easily find more focussed options using Google. The second item listed looked OK when I tried, if you don't mind Prolog, and there was at least one C example and one Javascript on the first page of results. And you can hardly claim not to know the words to Google for any more.

Answer 2

This is known as the Minimal Enclosing Circle problem (I'm puzzled why your google search didn't show up anything), and discussed here, here, here, and in many other places.