# Finding balls that contain a point

Suppose you are given a collection of $n$ balls in $\mathbb{R}^d$, and you want to preprocess them in such a way that you can later query them to find all spheres which contain any test point.

What efficient solutions are known for this problem?

The trivial answer is to just do a linear scan over all the spheres, which takes no preprocessing time but requires an overhead of $O(n)$ per query.

In 1D you can solve the problem using an interval tree, giving $O(\log(n) + k)$ query time with $O(n \log(n))$ preprocessing and $O(n)$ space, but it isn't clear to me that this generalizes.

I suspect there should be some sort of reduction here, since I can't seem to find any discussion of this problem in the literature which leads to me to think that it is trivial (though I am probably searching for the wrong terms).

There is a reduction to metric range searching in hyperbolic geometry with the signature $(+++ ... -)$, but I don't know how to do hyperbolic range searching efficiently (so it isn't much help).

If this question turns out to be too easy, you can also consider the situation where the set of balls is dynamic.

• are you looking at spheres or balls ? i.e a sphere is usually thought of as the surface of a ball. – Suresh Venkat May 8 '14 at 19:46
• @SureshVenkat balls, sorry for the confusion. – Mikola May 8 '14 at 19:47
• I suspect that the d = 2 (and possibly d = 3) case of this one might be much easier than the high dimensional case. In particular, for d = 2, you might be able to partition the plane to O(n) disjoint polygons (plus an infinite area) such that the inside of each polygon intersects the perimeter of at most one ball. – Zsbán Ambrus May 9 '14 at 12:18
• Unless you're doing some kind of approximation, how do you get a sublinear query time for this problem using kd-trees? In particular, suppose your dimension is two, your $n$ balls all have unit radius, their centers are evenly spaced on a circle of radius $1+1/n^2$ centered at the origin, and you query the origin. For this instance the output size is zero. Are you claiming that in this case, a kd-tree query that detects this fact can be performed in $O(\sqrt n)$ time? – David Eppstein May 9 '14 at 21:22
• @DavidEppstein oh man! You are completely correct, and what I wrote was wrong. – Mikola May 12 '14 at 18:06

## 1 Answer

Note that point location in an arrangement of balls (of different radii) is equivalent to point location in an arrangement of hyperplanes one dimension higher by using the usual paraboloid lifting map $(x_1, \ldots, x_d) \mapsto (x_1, \ldots, x_d, \sum_i x_i^2)$. If you call this lifting map $\Phi$, then it's easy to see that $p \in B$ if and only if $\Phi(p)$ is above $\Phi(B)$.

Now you have the problem of point location in an arrangement of hyperplanes (note that once you have such a structure it's usually easy to annotate each cell with the list of hyperplanes it is above). That problem can be solved by a variety of methods: for example there's an algorithm by Meiser that runs in time $O(d^5 \log n)$ but requires $n^d$ space. It's not clear from the question which is more important: space or time...

• Interesting, though maybe not immediately useful. I am looking for something with $O(n \log^c(n))$ preprocessing time/space so $O(n^d)$ is way too big. Still I am happy to learn about different approaches. I will go back to the question and update it. – Mikola May 8 '14 at 20:00
• If you want exact answers, I suspect you're doomed: you're either looking at linear space and near-linear query time, or (close to) log n query time and polynomial space. If you're willing to tolerate approximations of some kind, there might be hope. – Suresh Venkat May 8 '14 at 20:01
• @Saeed the complexity in his result should be $O(d^5 \log(n) + k)$, where $k$ is the number of returned points, same as the analysis for the complexity of range searching in a kdtree. – Mikola May 8 '14 at 20:04
• Actually in CG $d$ is used for dimension, not $k$ – Suresh Venkat May 8 '14 at 20:09
• k−d tree very explicitly k used for dimension — Only historically. The correct modern usage is "$d$-dimensional kd-tree". The letter k in "kd-tree" is not a variable; it's just part of the name of the data structure. See also: alpha-shape, beta-skeleton, k-set. – Jeffε May 9 '14 at 0:37