# Constrained Smallest Enclosing Ball Problem

Let $X = \{x_1, x_2, ..., x_n\} \subset \mathbb{R}^m$ be a finite set of points. Smallest enclosing ball is a well-known problem that asks for the $m$-ball that covers all $x_i \in X$, while having the smallest radius possible.

I am interested in solving a related, more constrained problem. Namely, in my version, the enclosing $m$-ball's center can not be chosen freely, but is constrained to be one of the points in $X$. In other words, I would like to find the point $x_j \in X$ such that the maximum distance (i.e. the enclosing radius)

$$\max_{x \text{ } \in \text{ } X} \; \lVert x - x_j \rVert$$

is minimized.

Obviously, one can simply compute all distances in $O(m n^2)$ time, and find the desired point. A less naive way to tackle the problem would be to generate a space-subdividing acceleration structure, say a kd-tree. We can do this in $O(m n \log n)$. Then, per-node maximum distances can be computed in $O(f(m, n))$ time, and we can pick the node having the minimum-maximum distance. This method would have a complexity of $O(n (f(m, n) + m \log n))$. Here, $f(m, n)$ is a function that stands for the query complexity of the kd-tree. Therefore, $f(m, n)$ "looks like" $m \log n$ for small $m$, but $m n$ for large $m$.

All in all, we would still be making many repeated (and unnecessary) distance computations. Also, because of how $f(m, n)$ behaves, the latter method degrades to the former for big $m$. Therefore, even the latter solution is not very satisfactory.

Can we do better? What is the best (in terms of time complexity and practical performance) known algorithm to tackle this problem?

• "ball" = "sphere"? – Raphael Dec 9 '15 at 21:52
• @Raphael: Yes. Some articles use balls, some articles use (hyper)spheres to formulate the same problem. Strictly speaking, a (hyper)sphere $S$ is some ball's (say $B$) boundary. So, in this formulation, when we say point $x$ in enclosed by ball $B$, we mean $x \in B$. One can uniquely identify a ball, and the (hyper)sphere that makes up its boundary, by a center point and a radius. These are the quantities we want to compute in the end. – iheap Dec 9 '15 at 21:59