Journal
COMPUTERS & GRAPHICS-UK
Volume 56, Issue -, Pages 1-10Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cag.2016.01.003
Keywords
Minimum enclosing ball; Acceleration techniques; Parallel processing; Computational geometry; Algorithms
Categories
Funding
- Swedish Foundation for Strategic Research [IIS11-0060]
- Swedish Foundation for Strategic Research (SSF) [IIS11-0060] Funding Source: Swedish Foundation for Strategic Research (SSF)
Ask authors/readers for more resources
We propose an algorithm for computing the exact minimum enclosing ball of large point sets in general dimensions. It aims to reduce the number of passes by retrieving a well-balanced set of outliers in each linear search through the input by decomposing the space into orthants. The experimental evidence indicates that the convergence rate in terms of the required number of linear passes is superior compared to previous exact methods, and substantially faster execution times are observed in dimensions d <= 16. In the important three-dimensional case, the execution times indicate real-time performance. Furthermore, we show how the algorithm can be adapted for parallel execution on both CPU and GPU architectures using OpenMP, AVX, and CUDA. For large datasets, our CUDA solution is superior. For example, the benchmark results show that optimal bounding spheres for inputs with tens of millions of points can be computed in just a few milliseconds. (C) 2016 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available