How can I find the minimal circle include some given points?

Question

I have given some points (2D-coordinates) and want to find the smallest circle, that includes all of this points. The algorithm doesn't have to be very efficient (while it would be nice naturally).

Answer 1

This is the so-called Smallest Enclosing Balls problem (in your case, Smallest Enclosing Circle), a.k.a. Miniball. There are several algorithms and implementations out there for this problem – all of the following are linear-time solutions (i.e., given n balls, they run in O(n) if you consider the dimension d fixed, d=2 in your case):

• For 2D and 3D, Gärtner's implementation is probably the fastest.

• For higher dimensions (up to 10,000, say), take a look at https://github.com/hbf/miniball, which is the implementation of an algorithm by Gärtner, Kutz, and Fischer (note: I am one of the co-authors).

• For very, very high dimensions, core-set (approximation) algorithms will be faster.

Note: If you are looking for an algorithm to compute the smallest enclosing sphere of spheres, you will find a C++ implementation in the Computational Geometry Algorithms Library (CGAL). (You do not need to use all of CGAL; simply extract the required header and source files.)