Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

abstract I describe a \texttt{C++} program for computing the smallest enclosing ball of a point set in $d$-dimensional space, using floating-point arithmetic only. The program is very fast for $d\leq 20$, robust and simple (about 300 lines of code, excluding prototype definitions). Its new features are a pivoting approach resembling the simplex method for linear programming, and a robust update scheme for intermediate solutions. The program with complete documentation following the \emph{literate programming} paradigm \cite{Knuth84} is available on the Web.

Back to the publications page