Back to my home page.
Approximating smallest enclosing balls with applications to machine learning
Frank Nielsen and Richard Nock
Abstract:
In this paper, we first survey previous work on computing the smallest enclosing balls in Euclidean spaces into three categories: combinatorial, numerical and hybrid coreset algorithms.
We then describe two novel tailored algorithms for computing arbitrary close approximations of the smallest enclosing Euclidean ball of balls.
The deterministic heuristics are based on solving relaxed decision problems using a primal-dual method interpreted geometrically as solving covering or dually piercing problems. Finally, we present some applications of the enclosing ball procedure in machine learning and discuss about its extensions to non-Euclidean information-theoretic spaces.
BibTex entry:
@InProceedings{MEBML-2007,
author = {Frank Nielsen and Richard Nock},
title = {Approximating smallest enclosing balls with applications to machine learning},
booktitle = {International Journal of Computational Geometry and its Applications (WorldScientific publisher)},
year = 2007,
note = {(invited paper)}
}
Last updated, February 2007.