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

Question

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

Answer 1

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.

Answer 2

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.