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,

|cite|improve this question
$\endgroup$
  • $\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
  • $\begingroup$ Thank you. I will look into it. $\endgroup$ – C.P. Dec 25 '18 at 15:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.