Faster Approximation of Minimum Enclosing Balls by Distance Filtering and GPU Parallelization

Abstract

Minimum enclosing balls are used extensively to speed up multidimensional data processing in, e.g., machine learning, spatial databases, and computer graphics. We present a case study of several acceleration techniques that are applicable in enclosing ball algorithms based on repeated farthest-point queries. Two different distance filtering heuristics are proposed aiming at reducing the cost of the farthest-point queries as much as possible by exploiting lower and upper distance bounds. Furthermore, auto-tunable GPU solutions using CUDA are developed for both low- and high-dimensional cases. Empirical tests apply these techniques to two recent algorithms and demonstrate substantial speedups of the ball computations. Our results also indicate that a combination of the approaches has the potential to give further performance improvements.

Additional information

Funding

Both authors are supported by a research grant from the Swedish Foundation for Strategic Research (No. IIS11-0060).