Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

abstract We develop a simple combinatorial algorithm for computing the smallest enclosing ball of a set of points in high dimensional Euclidean space. The resulting code is in most cases faster (sometimes significantly) than recent dedicated methods that only deliver approximate results, and it beats off-the-shelf solutions, based e.g.\ on quadratic programming solvers. The algorithm resembles the simplex algorithm for linear programming; it comes with a Bland-type rule to avoid cycling in presence of degeneracies and it typically requires very few iterations. We provide a fast and robust floating-point implementation whose efficiency is based on a new dynamic data structure for maintaining intermediate solutions. The code can efficiently handle point sets in dimensions up to $2,\!000$, and it solves instances of dimension $10,\!000$ within hours. In low dimensions, the algorithm can keep up with the fastest computational geometry codes that are available.