1
$\begingroup$

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,

Improve this question
$\endgroup$
3
  • $\begingroup$ When you say FPT, is f(d)polylog(|E|) ok? (I do not know of such a data structure) $\endgroup$ – daniello Dec 25 '18 at 14:58
  • 1
    $\begingroup$ Have you looked into the ‘nearest neighbor search’ literature? $\endgroup$ – daniello Dec 25 '18 at 15:01
  • 1
    $\begingroup$ 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 $\endgroup$ – Sasho Nikolov Dec 25 '18 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.