A Fast Smallest-Enclosing-Ball Algorithm for High Dimensions

a given finite set.

At ESA 2003, we presented a new combinatorial algorithm for this problem, which we have also tested in a C++ floating-point implementation. The resulting code is in most cases faster (sometimes significantly) than previous methods that only deliver approximate results, and it beats off-the-shelf solutions based on quadratic-programming solvers. It can handle instances with several thousand points in up to a few thousand dimensions.

Our algorithm resembles the simplex algorithm for linear programming; it comes with a Bland-type rule to avoid cycling in the presence of degeneracies and it typically requires very few iterations. We provide a fast and robust floating-point implementation whose efficiency stems from a new dynamic data structure based on dynamic QR-decompositions.

Joint work with Kaspar Fischer and Bernd G"artner from ETH Z"urich.