<p>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 <em>above</em> $\Phi(B)$. </p>

<p>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 <a href="http://www.sciencedirect.com/science/article/pii/S0890540183710576">algorithm by Meiser</a> 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...</p>

CC BY-SA 3.0
2014-05-08T20:00:04.860Z
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
CC BY-SA 3.0
2014-05-08T20:01:32.053Z
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
CC BY-SA 3.0
2014-05-08T20:01:55.903Z
If they all intersect in some points then given any of that points, output has size $n$, how can it be done in less than $\Omega(n)$? Is there any extra assumptions, Such as intersection of every 3 ball is empty? Or these algorithms are just for counting?
Saeed
CC BY-SA 3.0
2014-05-08T20:02:50.110Z
I would be happy with $O(n^{1-1/d})$ queries, though approximations could also be interesting.
Mikola
CC BY-SA 3.0
2014-05-08T20:04:06.897Z
@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
CC BY-SA 3.0
2014-05-08T20:07:39.523Z
@Mikola, OK, then is reasonable. Also $k$ is usually used for dimension ($k$ dimensional tree), and I think is somehow abusing a notation. (here in your question you have $d$ dimension).
Saeed
CC BY-SA 3.0
2014-05-08T20:09:54.053Z
Actually in CG $d$ is used for dimension, not $k$
Suresh Venkat
CC BY-SA 3.0
2014-05-08T20:12:36.743Z
@SureshVenkat as a follow up question: is it any easier to locate all planes containing a point in an arrangement than it is locate the cell containing the point?  If so, then it would seem there is still some hope this could be improved.
Mikola
CC BY-SA 3.0
2014-05-08T20:16:11.137Z
@SureshVenkat, As I know yes, $d$ is used for dimension in general. But for the particular case that I mentioned : $k-d$ tree very explicitly $k$ used for dimension. Actually it was better to leave my second comment on OPs question (because it's not clear what does he mean by $O(n^{1-1/d}+k)$, when talks about k-d tree. (OP either should write d-d tree and define the k, or introduce a new variable)
Saeed
CC BY-SA 3.0
2014-05-08T20:41:42.507Z
fair enough, but for most of us "in the business" the kd-tree terminology is just annoying :). Mikola's notation is standard ($d$ for dimension, $k$ for output size)
Suresh Venkat
CC BY-SA 3.0
2014-05-08T21:43:14.997Z
Yep, my misunderstading :) I was not familiar with this $k$ ;)
Saeed
CC BY-SA 3.0
2014-05-09T00:37:17.477Z
_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ε
CC BY-SA 3.0
2014-05-12T18:08:59.377Z
After thinking this over for a few days, I am now convinced this is the correct answer and feel a bit foolish for not seeing it sooner, since this reduction obviously works both ways.
Mikola
CC BY-SA 3.0
2014-05-20T23:09:58.763Z
This is the type of problem to use much machinery to get good theoretical but impractical bounds. In the case of disks in the plane, the lifting technique reduces it to finding the planes intersected by a vertical ray. We can get them one by one using vertical ray shooting from infinity and deleting planes/disks that are already reported. Chan's 3d dynamic convex hull (https://cs.uwaterloo.ca/~tmchan/dch3d.pdf) does these operations. The preprocessing is near-linear and the output is computed in time O(k several-logs(n)). This is only for the plane.
someone
CC BY-SA 3.0
2014-05-08T19:55:01.937Z
2014-05-08T19:55:01.937Z
Suresh Venkat
<p>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.</p>

<p>What efficient solutions are known for this problem?</p>

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

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

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

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

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

CC BY-SA 3.0
2014-05-08T19:46:25.660Z
are you looking at spheres or balls ? i.e a sphere is usually thought of as the surface of a ball.
Suresh Venkat
CC BY-SA 3.0
2014-05-08T19:47:15.323Z
@SureshVenkat balls, sorry for the confusion.
Mikola
CC BY-SA 3.0
2014-05-09T12:18:49.580Z
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
CC BY-SA 3.0
2014-05-09T21:22:04.840Z
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
CC BY-SA 3.0
2014-05-12T18:06:11.310Z
@DavidEppstein oh man!  You are completely correct, and what I wrote was wrong.
Mikola
CC BY-SA 4.0
2023-07-26T09:41:27.597Z
Is there a simple answer in case all balls have the same radius?
daruma
<cg.comp-geom>
Finding balls that contain a point
Mikola
# Finding balls that contain a point

(Asked by: username_0 on 2014-05-08)

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.

**Tags:** cg.comp-geom

> **Comments:**
> **username_1**: are you looking at spheres or balls ? i.e a sphere is usually thought of as the surface of a ball.  
> **username_0**: @SureshVenkat balls, sorry for the confusion.  
> **username_2**: 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.  
> **username_3**: 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?  
> **username_0**: @DavidEppstein oh man!  You are completely correct, and what I wrote was wrong.  
> **username_4**: Is there a simple answer in case all balls have the same radius?  

---

## 1 answers

### Answer by username_1 on 2014-05-08. Score: 7 | Accepted 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](http://www.sciencedirect.com/science/article/pii/S0890540183710576) 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...

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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.  
> **username_5**: If they all intersect in some points then given any of that points, output has size $n$, how can it be done in less than $\Omega(n)$? Is there any extra assumptions, Such as intersection of every 3 ball is empty? Or these algorithms are just for counting?  
> **username_0**: I would be happy with $O(n^{1-1/d})$ queries, though approximations could also be interesting.  
> **username_0**: @username_5 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.  
> **username_5**: @username_0, OK, then is reasonable. Also $k$ is usually used for dimension ($k$ dimensional tree), and I think is somehow abusing a notation. (here in your question you have $d$ dimension).  
> **username_1**: Actually in CG $d$ is used for dimension, not $k$  
> **username_0**: @SureshVenkat as a follow up question: is it any easier to locate all planes containing a point in an arrangement than it is locate the cell containing the point?  If so, then it would seem there is still some hope this could be improved.  
> **username_5**: @SureshVenkat, As I know yes, $d$ is used for dimension in general. But for the particular case that I mentioned : $k-d$ tree very explicitly $k$ used for dimension. Actually it was better to leave my second comment on OPs question (because it's not clear what does he mean by $O(n^{1-1/d}+k)$, when talks about k-d tree. (OP either should write d-d tree and define the k, or introduce a new variable)  
> **username_1**: fair enough, but for most of us "in the business" the kd-tree terminology is just annoying :). username_0's notation is standard ($d$ for dimension, $k$ for output size)  
> **username_5**: Yep, my misunderstading :) I was not familiar with this $k$ ;)  
> **username_6**: _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.  
> **username_0**: After thinking this over for a few days, I am now convinced this is the correct answer and feel a bit foolish for not seeing it sooner, since this reduction obviously works both ways.  
> **username_7**: This is the type of problem to use much machinery to get good theoretical but impractical bounds. In the case of disks in the plane, the lifting technique reduces it to finding the planes intersected by a vertical ray. We can get them one by one using vertical ray shooting from infinity and deleting planes/disks that are already reported. Chan's 3d dynamic convex hull (https://cs.uwaterloo.ca/~tmchan/dch3d.pdf) does these operations. The preprocessing is near-linear and the output is computed in time O(k several-logs(n)). This is only for the plane.  

---

