An external memory algorithm for the minimum enclosing ball problem
2016 (English)In: VISIGRAPP 2016 - Proceedings of the 11th Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications, 2016, p. 83-90Conference paper, Published paper (Refereed)
Resource type
Text
Abstract [en]
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.
Place, publisher, year, edition, pages
2016. p. 83-90
Keywords [en]
Big Data, External Memory Algorithm, Minimum Enclosing Ball, Smallest Bounding Sphere, Computation theory, Computer graphics, Computer vision, External memory algorithms, Near-optimal, Out-of-core algorithms, Simple heuristics, Test case, Three dimensional data sets, Algorithms
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:mdh:diva-31792DOI: 10.5220/0005675600810088Scopus ID: 2-s2.0-84968830542ISBN: 9789897581755 (print)OAI: oai:DiVA.org:mdh-31792DiVA, id: diva2:934597
Conference
11th International Conference on Computer Graphics Theory and Application, GRAPP 2016; Part of the 11th Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications, VISIGRAPP 2016, 27 February 2016 through 29 February 2016
2016-06-092016-06-092021-03-22Bibliographically approved