Graphics Reference
In-Depth Information
sphere for the point set
P
. Welzl's algorithm is based on this observation,
resulting in a recursive algorithm. It proceeds by maintaining both the set of input
points and a
set of support
, which contains the points from the input set that must
lie on the boundary of the minimum sphere. The following code fragment outlines
Welzl's algorithm:
∪ {
Q
}
Sphere WelzlSphere(Point pt[], unsigned int numPts, Point sos[], unsigned int numSos)
{
// if no input points, the recursion has bottomed out. Now compute an
// exact sphere based on points in set of support (zero through four points)
if (numPts == 0) {
switch (numSos) {
case 0: return Sphere();
case 1: return Sphere(sos[0]);
case 2: return Sphere(sos[0], sos[1]);
case 3: return Sphere(sos[0], sos[1], sos[2]);
case 4: return Sphere(sos[0], sos[1], sos[2], sos[3]);
}
}
// Pick a point at "random" (here just the last point of the input set)
int index = numPts - 1;
// Recursively compute the smallest bounding sphere of the remaining points
Sphere smallestSphere = WelzlSphere(pt, numPts - 1, sos, numSos);
// (*)
// If the selected point lies inside this sphere, it is indeed the smallest
if(PointInsideSphere(pt[index], smallestSphere))
return smallestSphere;
// Otherwise, update set of support to additionally contain the new point
sos[numSos] = pt[index];
// Recursively compute the smallest sphere of remaining points with new s.o.s.
return WelzlSphere(pt, numPts - 1, sos, numSos + 1);
}
Although the two recursive calls inside the function make the function appear
expensive, Welzl showed that assuming points are removed from the input set at
random the algorithm runs in expected linear time. Note that, as presented, the first
recursive call (marked with an asterisk in the code) is likely to cause stack overflow
for inputs of more than a few thousand points. Slight changes to the code avoid this
problem, as outlined in [Gärtner99]. A full implementation is given in [Capens01].
Also available on the Internet is a more intricate implementation, part of the Com-
putational Geometry Algorithms Library (CGAL). Writing a robust implementation
of Welzl's algorithm requires that the four support functions for computing exact
spheres from one through four points must correctly deal with degenerate input,
such as collinear points.
