minimal graph on spatial points

Question

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.

Answer 1

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.

Answer 2

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?

Answer 3

It 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.