Smallest circle which covers given points on 2D plane

Question

Problem: What is the smallest possible diameter of a circle which covers given N points on a 2D plane?

What is the most efficient algorithm to solve this problem and how does it work?

Answer 1

This is the smallest circle problem. See the references for the links to the suggested algorithms.

E.Welzl, Smallest Enclosing Disks (Balls and Ellipsoids), in H. Maurer (Ed.), New Results and New Trends in Computer Science, Lecture Notes in Computer Science, Vol. 555, Springer-Verlag, 359–37 (1991)

is the reference to the "fastest" algorithm.

Answer 2

There are several algorithms and implementations out there for the Smallest enclosing balls problem.

• 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.)