# Points of a finite set wihtin a ball

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

• When you say FPT, is f(d)polylog(|E|) ok? (I do not know of such a data structure) – daniello Dec 25 '18 at 14:58
• Have you looked into the ‘nearest neighbor search’ literature? – daniello Dec 25 '18 at 15:01
• 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 arxiv.org/pdf/1806.09823.pdf – Sasho Nikolov Dec 25 '18 at 15:16