5
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ "ball" = "sphere"? $\endgroup$
    – Raphael ♦
    Dec 9, 2015 at 21:52
  • 1
    $\begingroup$ @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. $\endgroup$
    – iheap
    Dec 9, 2015 at 21:59

1 Answer 1

Reset to default
1
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ The approach you suggested is analyzed in this paper. As discussed in the paper, one can even make certain approximation guarantees here. However, to find the exact solution, one might still need to check all nodes (and their enclosing radii) as the approximation gets tighter and tighter. $\endgroup$
    – iheap
    Dec 11, 2015 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.