Given N points in a 3D space, how to find the smallest sphere that contains these N points?

Giv开发者_开发问答en N points in a 3D space, how to find the smallest sphere that contains these N points?

This problem is called minimal enclosing ball problem. (google this term to find tutorials and papers on it).

Here's one implementation: http://www.inf.ethz.ch/personal/gaertner/miniball.html in c++.

Its 2d case (find a circle to enclose all points in a plane) is a classic example taught in computational geometry course. 3D is just a simple extension to the 2D case.

One algorithm for this problem is incremental style. You start with 4 points and they fix a sphere, and when you add 5-th point, there are two cases:

1. the point is in the sphere. no need to update.

2. outside the point. In this case, you need to update your sphere. Then a non-trivial property is that this new point must be on your new sphere!

Based on the above observation, your problem gets smaller. Read section 4.7 of this book. It is also available on google book.

The problem boils down to finding the convex hull of the N points. Most of the convex hull algorithms like divide and conquer, gift wrapping or Jarvis March and Timothy Chan's algorithms can be applied to 3D too. Of all these algorithms Timothy Chan's algorithm is the best algorithm known.

There are several algorithms and implementations out there for this 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.)