abstract
We develop algorithms for computing the smallest enclosing ball of a
set of $n$ balls in $d$-dimensional space. Unlike previous methods,
we explicitly address small cases ($n\leq d+1$), derive the necessary
primitive operations and show that they can efficiently be realized
with rational arithmetic. An exact implementation (along with a fast
\footnote{For $d=3$, a set of $1,000,000$ balls is processed in
less than two seconds on a modern PC.}
and robust floating-point version) is available as standalone code
and as part of the CGAL library.
Our algorithms are based on novel insights into the combinatorial
structure of the problem. As it turns out, results for smallest
enclosing balls of points do not extend as one might expect.
For example, we show that Welzl's randomized linear-time algorithm
for computing the ball spanned by a set of points fails to work for balls.
Consequently, David White's adaptation of the method to the ball
case (as the only available implementation so far it is mentioned
in many link collections) is incorrect and may crash or, in the
better case, produce wrong balls.
In solving the small cases we may assume that the ball centers are
affinely independent; in this case, the problem is surprisingly
well-behaved: via a geometric transformation and suitable
generalization, it fits into the combinatorial model of
\emph{unique sink orientations} whose rich structure has
recently received considerable attention. One consequence is
that Welzl's algorithm \emph{does} work for small instances;
moreover, there is a wide variety of \emph{pivoting} methods for
unique sink orientations which have the potential of being fast
in practice even for high dimensions.
As a by-product, we show that the problem of finding the smallest
enclosing ball of balls is computationally equivalent to the problem
Back to the publications page
