@article{2009-EnclosingBallMachineLearning-IJCGA
, author={Frank Nielsen and Richard Nock}
, title={Approximating smallest enclosing balls with applications to machine learning}
, journal={International Journal on Computational Geometry and Applications}
, month={October}
, year={2009}
, volume={19}
, number={5}
, pages={389-414
}
, doi={10.1142/S0218195909003039}
, abstract={
  In this paper, we first survey prior work for computing exactly or approximately
 the smallest enclosing balls of point or ball sets in Euclidean spaces. We classify
 previous work into three categories: (1) purely combinatorial, (2) purely numerical,
 and (3) recent mixed hybrid algorithms based on coresets. We then describe two novel
 tailored algorithms for computing arbitrary close approximations of the smallest
 enclosing Euclidean ball of balls. These deterministic heuristics are based on solving
 relaxed decision problems using a primal-dual method. The primal-dual method is
 interpreted geometrically as solving for a minimum covering set, or dually as seeking
 for a minimum piercing set. Finally, we present some applications in machine learning
 of the exact and approximate smallest enclosing ball procedure, and discuss about
 its extension to non-Euclidean information- theoretic spaces.
  }
}