Linus Källberg
Mälardalen University, Sweden
Thomas Larsson
Mälardalen University, Sweden
Download article
Published in: Proceedings of SIGRAD 2014, Visual Computing, June 12-13, 2014, Göteborg, Sweden
Linköping Electronic Conference Proceedings 106:8, p. 57-65
Published: 2014-10-30
ISBN: 978-91-7519-212-3
ISSN: 1650-3686 (print), 1650-3740 (online)
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. Parallel GPU solutions using CUDA are developed for both low- and high-dimensional cases. Furthermore, 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. Empirical tests show encouraging results. Compared to a sequential CPU version of the algorithm, the GPU parallelization runs up to 11 times faster. When applying the distance filtering techniques, further speedups are observed.
