Given a collection of thousands of points in 3D, I need to get the list of neighbours for each particle that fall inside some cutoff value (in terms of euclidean distance), and if possible, sorted from nearest fo farthest.
Which is the fastest parallel algorithm for this purpose?
PS: I also crossposted this in math exchange and SO
This is the well-studied problem of Nearest Neighbour Search. There is not one 'best solution' to the problem---you'll want to choose trade offs based on the input and requirements.
Do you need the creation of the data structure to be parallel? Or just the queries? Depending on how many thousands of points you're talking about, if your set of points is static it might not be impractical to do something naive like:
This can be done in $O(n^2\log n)$ time and $O(n^2)$ space, which is not that bad if you only need to run it once for a set of several thousand points. It will give you constant or logarithmic query time for pretty much anything you'd want to do.
If you need something smarter that requires less space or less time, I'd recommend reading the Wikipedia article on Nearest Neighbour Search and perhaps refining your question, telling us
External links referenced by this document: