In this article we present an external memory algorithm for computing the exact minimum enclosing ball of a massive set of points in any dimension. We test the performance of the algorithm on real-life three-dimensional data sets and demonstrate for the first time the practical efficiency of exact out-of-core algorithms. By use of simple heuristics, we achieve near-optimal I/O in all our test cases.
Authors and Affiliations
- Linus Källberg, Mälardalen University, Sweden
- Evan Shellshear, Fraunhofer Chalmers Centre, Sweden
- Thomas Larsson, Mälardalen University, Sweden