minimal graph on spatial points
https://stackoverflow.com/questions/1260548
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
I have a set of 3 dimensional points. I want a quick query of the k nearest neighbours of any of these points. I know that a usual way of doing this is oct-tree, however I think that with the below described data structure the query would be much faster.
I want a minimal graph on the points as vertices, which have the following property:
Between any 2 points P1, P2: there is a path in which for all interior point P3:
distance(P1, P3) <= distance(P1, P2).
My problem though is that I cannot figure out how to compute this minimal graph in an affordable time.
Solution 3
7 years later i think i can answer my own question :
The graph i was looking for is called monotone proximity graph - the most known example is the Delaunay triangulation/tetrahedralization.
Compared to space-partition trees: such a graph provides faster query time but needs more memory, takes much more time and computation may fail because of degeneracy problems.
Due to these problems of them, i think generally their application to speed up KNN queries is not advisable, and one should simply use kd-trees.
OTHER TIPS
That's because there is no silver bullet.
You can do relatively slow queries with no previous computation or fast queries with lots of previous computations and backing data structures. It's up to you to choose.
It sounds like all you're asking for is the points within some distance of another point. d(P1, P2) is just a number, so all points within that distance from P1 would satisfy your criteria.
If you need to run the search many times and from multiple starting points, then you should look into the standard data structures like kd trees. If you're executing it only once, then just iterating over all points might be your best bet.
What was the application you had in mind?
