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 update process

Up until now we've been discussing the algorithm but assumed the update process gives the smallest enclosing sphere from the points in the set plus the new point P that was added to the set.

The update process attempts to find the smallest sphere by computing all combinations of spheres possible from the set plus the new point P, now a new set. Depending on the number of points in the set, the possible permutations for a 2D circle are (assuming the points in the set are p0, p1…):

• If the set has one point and P is added we now have two points defining the circle.
• If the set has two points and P is added we now have three points. The minimum circle can now be defined by (p0, P), (p1, P) or in case the minimum circle is not one of them, it will be defined by (p0, p1, P).
• If the set has three points and P is added we now have four possible points. The circle can be defined by: (p0, p3) if p1 and p2 are within it, (p1, p3) if p0 and p2 are within it, (p2, p3) if p0 and p1 are within it, (p0, p1, p3) if p2 is within it, (p0, p2, p3) if p1 is within it, (p1, p2, p3) if p0 is within it, for a total of six permutations (three circles defined by two points and three defined by three points)
• In 3D only – The set may contain four points when P is added to it, giving a total of five points. Since up to four points can be used to define the sphere there are a total of 14 possible permutations.

Once a new optimal sphere is found from the new set of points it also uniquely determines which points should be removed from the set because they are no longer on the perimeter of the sphere – thus not support points.

For example, assume the set has three points when P is added to it. There are effectively four points to use for a total of 6 possible circles. Let's also assume that the optimal sphere out of the 6 spheres is the first permutation defined by (p0, P), where P is p3 (the set contains p0, p1, p2 and the new p3).

The new set should then become (p0, p3 = P) since the sphere was found to be defined by two points and the permutation is (p0, p3). The set is resized to a size of 2 and since p0 was already there, p3 replaces the other point that is in the set. In the same manner it is easy to understand the rest of the permutations, which points should be in the updated support set and which are removed.

The only problem left to solve is how to generate a sphere/circle from a given amount of input points. Our initial condition requires us to use one point (the set will initially contain one point). The permutations given above suggest we need a way to define spheres from two points and even three points.

Generating a sphere from a set of points

In this section I'll briefly describe the possible ways to create a sphere based on a number of points. As shown earlier we need functions to create a sphere from one, two and three input points (as well as four in 3D). These can be implemented by constructors of a sphere class or update functions to an existing sphere (to save object construction destruction).

Depending on the number of points these are the steps used to create the sphere:

• For one point the sphere's center is set to be the point and the radius is 0. This is the algorithm's initial condition.
• For two points the center is selected to be halfway between the two points, while the radius is set to be half the length of the vector connecting the points.
• For three points we define the center in barycentric coordinates:
  
  C = u0 * p0 + u1 * p1 + u2 * p2, where u0 + u1 + u2 = 1
  
  The radius is: R = |C-p0| = |C-p1| = |C-p2|.
  
  Using some algebra it is possible to get a system of two equations that are quite easily solved. The full details of the derivation are easy to find as the problem is well studied in computational geometry.
  
  A very good reference for this is "Geometric Tools for Computer Graphics" by David Eberly [Ebe03].

Page 4