空间点的最小图
我有一组 3 维点。 我想要快速查询这些点中任意点的 k 个最近邻点。 我知道执行此操作的常用方法是八叉树，但是我认为使用下面描述的数据结构，查询会快得多。
我想要一个以点为顶点的最小图，它具有以下属性：
在任意 2 点 P1、P2 之间：存在一条路径，其中对于所有内部点 P3：
距离(P1, P3) <= 距离(P1, P2）。
但我的问题是，我无法弄清楚如何在负担得起的时间内计算这个最小图。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
那是因为没有灵丹妙药。
您可以在没有先前计算的情况下执行相对较慢的查询，也可以在有大量先前计算和支持数据结构的情况下执行快速查询。 由你来选择。
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.
听起来您所要求的只是距另一个点一定距离内的点。 d(P1, P2) 只是一个数字，因此距 P1 的距离内的所有点都满足您的条件。
如果您需要多次从多个起点运行搜索，那么您应该查看标准数据结构，例如 kd 树。 如果您只执行一次，那么迭代所有点可能是您最好的选择。
您想要的应用程序是什么？
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?
7 年后，我想我可以回答我自己的问题：
我正在寻找的图称为单调邻近图 - 最著名的例子是 Delaunay 三角剖分/四面体化。
与空间分区树相比：这样的图提供更快的查询时间，但需要更多的内存，花费更多的时间，并且由于简并问题，计算可能会失败。
由于它们的这些问题，我认为通常不建议使用它们来加速 KNN 查询，而应该简单地使用 kd 树。
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.