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?