<p>I am looking for data-structures to store efficiently a set of points <span class="math-container">$E$</span> in an euclidean space of dimension <span class="math-container">$d$</span>.
In particular, I would like to be able to solve the problem of finding all the point within a ball of center p and radius n without exploring all the points of <span class="math-container">$E$</span>.</p>

<ul>
<li>First remark that it depends of the choice of the distance: it is much more easier for the <a href="https://en.wikipedia.org/wiki/Chebyshev_distance" rel="nofollow noreferrer">Chebyshev distance</a> since a simple b-tree over each coordinates would be sufficient.</li>
<li>Also remark that I would be happy if finding those points is FPT with the <span class="math-container">$d$</span> (dimension) as a parameter.  </li>
</ul>

<p>I guess it is <em>well-known-well-studied</em> problem, but I didn't find anything after a (rather short) bibliographical search?</p>

<p>Best, </p>

CC BY-SA 4.0
2018-12-25T14:58:26.330Z
When you say FPT, is f(d)polylog(|E|) ok? (I do not know of such a data structure)
daniello
CC BY-SA 4.0
2018-12-25T15:01:20.150Z
Have you looked into the ‘nearest neighbor search’ literature?
daniello
CC BY-SA 4.0
2018-12-25T15:16:35.940Z
This sounds like near neighbor search, indeed. The exact problem can be solved in space $n^{O(d)}$ and query time $d^{O(1)} \log n$ per output point. Achieving subexponential space and sublinear query time is known to be hard assuming some complexity conjectures. If you allow approximations then you can do a lot better. Check this recent survey for references https://arxiv.org/pdf/1806.09823.pdf
Sasho Nikolov
<ds.data-structures><computational-geometry><metric-spaces>
Points of a finite set wihtin a ball
C.P.
# Points of a finite set wihtin a ball

(Asked by: username_0 on 2018-12-25)

I am looking for data-structures to store efficiently a set of points $E$ in an euclidean space of dimension $d$.
In particular, I would like to be able to solve the problem of finding all the point within a ball of center p and radius n without exploring all the points of $E$.

* First remark that it depends of the choice of the distance: it is much more easier for the [Chebyshev distance](https://en.wikipedia.org/wiki/Chebyshev_distance) since a simple b-tree over each coordinates would be sufficient.
* Also remark that I would be happy if finding those points is FPT with the $d$ (dimension) as a parameter.

I guess it is *well-known-well-studied* problem, but I didn't find anything after a (rather short) bibliographical search?

Best,

**Tags:** ds.data-structures, computational-geometry, metric-spaces

> **Comments:**
> **username_1**: When you say FPT, is f(d)polylog(|E|) ok? (I do not know of such a data structure)  
> **username_1**: Have you looked into the ‘nearest neighbor search’ literature?  
> **username_2**: This sounds like near neighbor search, indeed. The exact problem can be solved in space $n^{O(d)}$ and query time $d^{O(1)} \log n$ per output point. Achieving subexponential space and sublinear query time is known to be hard assuming some complexity conjectures. If you allow approximations then you can do a lot better. Check this recent survey for references https://arxiv.org/pdf/1806.09823.pdf  

---

## 0 answers

