On the elimination of inessential points in the smallest enclosing ball problem

Abstract

We consider the construction of the smallest ball ${\mathcal{B}}^{\ast }$ enclosing a set ${\mathcal{X}}_n$ formed by n points in ${\mathbb{R}}^d$. We show that any probability measure on ${\mathcal{X}}_n$, with mean c and variance matrix V, provides a lower bound b on the distance to c of any point on the boundary of ${\mathcal{B}}^{\ast }$, with b having a simple expression in terms of c and V. This inequality permits to remove inessential points from ${\mathcal{X}}_n$, which do not participate to the definition of ${\mathcal{B}}^{\ast }$, and can be used to accelerate algorithms for the construction of ${\mathcal{B}}^{\ast }$. We show that this inequality is, in some sense, the best possible. A series of numerical examples indicates that, when d is reasonably small ($d\le 10$, say) and n is large (up to ${10}^5$), 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.

Keywords:

• minimum enclosing ball
• smallest ball
• Chebyshev centre
• core sets
• optimal design of experiments

AMS Subject Classification:

• 90C25
• 90C46
• 62K05

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 [2].

Disclosure statement

No potential conflict of interest was reported by the author.

Notes

1. There may exist $\xi \ne \nu$ such that $\phi \left(\xi \right)=\phi \left(\nu \right)$ and $c\left(\xi \right)=c\left(\nu \right)$, and then $g\left(\alpha \right)$ is constant for all $\alpha \in [0,1]$ (think for example of ${\mathcal{X}}_n$ given by the vertices of several regular simplices in ${\mathbb{R}}^d$ all having the same centre).

2. Although the value $\sigma =\sqrt{7}/2$ gives a tight bound, one may notice that the inequality (27(27) $\parallel X_i-c\left({\xi }_2\right)\parallel <0.133974\parallel X_{i_2}-X_{i_1}\parallel <\sqrt{7-4\sqrt{3}}\parallel X_{i_2}-X_{i_1}\parallel /2$(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 6 and 9.

4. See also the implementation in http://doc.cgal.org/latest/Bounding_volumes/classCGAL_1_1Min_sphere__d.html