Constrained Smallest Enclosing Ball Problem

Question

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?

Answer 1

I guess one simple approach would be to use any known Smallest Ball algorithm to determine the center of the optimal ball. Then you use kNN-queries to find the closest neighbour, which is likely the required point. However, you would need to show that the closest neighbour really is necessarily the best point. Maybe you need to actually check a number of candidates within a to-be-determined distance of the virtual center point.

Also, for a practical solution, I wouldn't use a kd-tree. R-Tree (or R*tree/R+tree/X-tree) behave better, so does the PH-Tree (a kind of quadtree).