Smallest circle which covers given points on 2D plane

Problem: What is the smallest possible diameter of a circle which covers 开发者_StackOverflow社区given N points on a 2D plane?

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

---

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.

---

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

---

the furthest point voronoi diagram approach

http://www.dma.fi.upm.es/mabellanas/tfcs/fvd/algorithm.html

turns out to work really well for the 2 d problem. It is non-iterative and (pretty sure) guaranteed exact. I suspect it doesn't extend so well to higher dimensions, which is why there is little attention to it in the literature.

If there is interest i'll describe it here - the above link is a bit hard to follow I think.

edit another link: http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/6704