6
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ are you looking at spheres or balls ? i.e a sphere is usually thought of as the surface of a ball. $\endgroup$
    – Suresh Venkat
    Commented May 8, 2014 at 19:46
  • $\begingroup$ @SureshVenkat balls, sorry for the confusion. $\endgroup$
    – Mikola
    Commented May 8, 2014 at 19:47
  • $\begingroup$ 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. $\endgroup$
    – Zsbán Ambrus
    Commented May 9, 2014 at 12:18
  • 3
    $\begingroup$ 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? $\endgroup$
    – David Eppstein
    Commented May 9, 2014 at 21:22
  • $\begingroup$ @DavidEppstein oh man! You are completely correct, and what I wrote was wrong. $\endgroup$
    – Mikola
    Commented May 12, 2014 at 18:06

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
14
  • $\begingroup$ 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. $\endgroup$
    – Mikola
    Commented May 8, 2014 at 20:00
  • 4
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented May 8, 2014 at 20:01
  • 1
    $\begingroup$ @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. $\endgroup$
    – Mikola
    Commented May 8, 2014 at 20:04
  • 1
    $\begingroup$ Actually in CG $d$ is used for dimension, not $k$ $\endgroup$
    – Suresh Venkat
    Commented May 8, 2014 at 20:09
  • 2
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Commented May 9, 2014 at 0:37

Your Answer

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

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