An External Memory Algorithm for the Minimum Enclosing Ball Problem

Linus Källberg, Evan Shellshear, Thomas Larsson

2016

Abstract

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.

Paper Citation

in Harvard Style

Källberg L., Shellshear E. and Larsson T. (2016). An External Memory Algorithm for the Minimum Enclosing Ball Problem . In Proceedings of the 11th Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2016) ISBN 978-989-758-175-5, pages 83-90. DOI: 10.5220/0005675600810088

in Bibtex Style

@conference{grapp16,
author={Linus Källberg and Evan Shellshear and Thomas Larsson},
title={An External Memory Algorithm for the Minimum Enclosing Ball Problem},
booktitle={Proceedings of the 11th Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2016)},
year={2016},
pages={83-90},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005675600810088},
isbn={978-989-758-175-5},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 11th Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications - Volume 1: GRAPP, (VISIGRAPP 2016)
TI - An External Memory Algorithm for the Minimum Enclosing Ball Problem
SN - 978-989-758-175-5
AU - Källberg L.
AU - Shellshear E.
AU - Larsson T.
PY - 2016
SP - 83
EP - 90
DO - 10.5220/0005675600810088