Graphics Reference
In-Depth Information
RitterSphere(s, pt, numPts);
Sphere s2 = s;
for(intk=0;k<NUM_ITER; k++) {
// Shrink sphere somewhat to make it an underestimate (not bound)
s2.r = s2.r * 0.95f;
// Make sphere bound data again
for(inti=0;i<numPts; i++) {
// Swap pt[i] with pt[j], where j randomly from interval [i+1,numPts-1]
DoRandomSwap();
SphereOfSphereAndPt(s2, pt[i]);
}
// Update s whenever a tighter sphere is found
if (s2.r < s.r)s=s2;
}
}
To further improve the results, the points are considered at random, rather than in
the same order from iteration to iteration. The resulting sphere is usually much better
than that produced by Wu's method (described in the previous section), at the cost of
a few extra iterations over the input data. If the same iterative approach is applied to
Wu's algorithm, the results are comparable. As with all iterative hill-climbing algo-
rithms of this type (such as gradient descent methods, simulated annealing, or TABU
search), the search can get stuck in local minima, and an optimal result is not guar-
anteed. The returned result is often very nearly optimal, however. The result is also
very robust.
4.3.5
The Minimum Bounding Sphere
A sphere is uniquely defined by four (non co-planar) points. Thus, a brute-force
algorithm for computing the minimum bounding sphere for a set of points is to
consider all possible combinations of four (then three, then two) points, computing
the smallest sphere through these points and keeping the sphere if it contains all other
points. The kept sphere with the smallest radius is then the minimum bounding
sphere. This brute-force algorithm has a complexity of
O
(
n
5
) and is therefore not
practical. Fortunately, the problem of computing the minimum bounding sphere for
a set of points has been well studied in the field of computational geometry, and a
randomized algorithm that runs in expected linear time has been given by [Welzl91].
Assume a minimum bounding sphere
S
has been computed for a point set
P
.Ifa
new point
Q
is added to
P
, then only if
Q
lies outside
S
does
S
need to be recomputed. It
is not difficult to see that
Q
must lie on the boundary of the new minimum bounding
