Abstract
We consider the construction of the smallest ball enclosing a set formed by n points in . We show that any probability measure on , with mean c and variance matrix V, provides a lower bound b on the distance to c of any point on the boundary of , with b having a simple expression in terms of c and V. This inequality permits to remove inessential points from , which do not participate to the definition of , and can be used to accelerate algorithms for the construction of . We show that this inequality is, in some sense, the best possible. A series of numerical examples indicates that, when d is reasonably small (, say) and n is large (up to ), the elimination of inessential points by a suitable two-point measure, followed by a direct (exact) solution by quadratic programming, outperforms iterative methods that compute an approximate solution by solving the dual problem.
Acknowledgements
The author thanks the two referees for their comments that helped to improve the presentation of the paper. He also thanks the referee who pointed out the existence of reference [Citation2].
Disclosure statement
No potential conflict of interest was reported by the author.
Notes
1. There may exist such that and , and then is constant for all (think for example of given by the vertices of several regular simplices in all having the same centre).
2. Although the value gives a tight bound, one may notice that the inequality (Equation27(27) (27) ) is suboptimal since the worst-case situations in Theorem 3.3 and Lemma .1 correspond to different measures.
3. The same observation can be made in Tables and .
4. See also the implementation in http://doc.cgal.org/latest/Bounding_volumes/classCGAL_1_1Min_sphere__d.html