Welzl's Minimum Sphere Algorithm Demystified
by Eli Kara

Contents   Page 1   Page 2   Page 3   Page 4   Source code   Printable version   Discuss this article

The optimal solution

A better solution to the problem is to grow a sphere to contain all the input points. The solution sounds simple enough and is fairly easy to visualize. Every time the sphere is grown to contain a new point, the sphere is updated. Points that were inside the sphere might find themselves outside the new sphere since the center and the radius might both change.

For this reason, the algorithm is restarted and the input points are tested against the sphere again. Any point that lies within it is ignored, while a point that lies outside will trigger a new update just as before. A new point P will then cause the sphere to grow and include P.

Visually the two cases before and after the update might look like this:

The circle on the left represents the sphere before it was updated with point P. The sphere is currently defined by only two points but it is clearly the optimal sphere containing all the points at this time (a sphere in 2D is uniquely defined by three points, four in 3D so there is no need for more than three).

Once a new point P is introduced, the sphere should grow to contain the new point. Since there is no logic in growing the sphere more than necessary, point P is considered to be on the sphere itself. On the right we can see the new sphere, now defined by P and the left-most point from the earlier case.

Growing the sphere is not a trivial operation. In fact, by just making the radius larger and not changing the center, the new sphere will not be optimal as the left-most point (that was on the sphere itself) will no longer be on it but inside it.

In order to prevent this and find an optimal sphere the algorithm defines a support set that contains points (called support points). Supporting points are defined as points that lie on the sphere perimeter (lie on the sphere). In the smaller sphere there were two supporting points. After the sphere has grown we have to add point P to the support points (since it is on the sphere) and recalculate the sphere from the points in the set.

Since the set after the addition now contains three points the only problem left is to find the minimum sphere from the three points and if not found, from two points, etc.

Since the number of points in the set is only three, the number of permutations to test is not large and thus we find the new optimal sphere. Note however that the new optimal sphere calculated from the set of three points may be defined by only two points. This is the case shown on the right.

When a new point was added (P), the set now contains three points but the minimum sphere is found by only using two points (one of the permutations). Therefore, one of the supporting points before the update is no longer a supporting point since it's not on the sphere and gets removed from the set.

The update procedure is therefore responsible for the following tasks:

• Add the new point P to the support set
• Compute the minimum sphere from the new set
• Any points from the set not on the sphere perimeter after the new sphere is computed are removed from the set

The algorithm stops only when a sphere is found that includes all points from the input set (some lie on the sphere itself). Naturally, the algorithm's last iteration processes all the points not in the set and ignored them as being inside the sphere.

Time complexity

If the number of algorithm restarts mis effectively small compared to the number of input points, the algorithm is then considered to have a linear running time. However, if the algorithm needs to restart after every update then the running time is effectively squared, O(n2).

In order to ensure that the input points have only a small chance of being arranged in a way that gives the worst-case running time, the points are shuffled in a random order. Welzl showed that if the points have a random ordering then the algorithm runs in expected linear time, a total running time of O(m * n). It is important to note that the update process itself in which the algorithm uses the points in the support set plus the new point to find the new minimum sphere is bounded since the number of points in the set is small (a maximum of 4 in 2D and 5 in 3D) and the number of possible spheres is rather small. Since m is the number of restarts it is also the number of update operations.

Page 3