我有一组 3 维点。我想快速查询任何这些点的 k 个最近邻居。我知道这样做的常用方法是八叉树，但是我认为使用下面描述的数据结构，查询会快得多。
我想要一个关于点的最小图作为顶点，它具有以下属性：
在任意 2 点 P1、P2 之间：对于所有内部点 P3，存在一条路径：
距离（P1，P3）<= 距离（P1，P2）。
但我的问题是我无法弄清楚如何在可承受的时间内计算这个最小的图表。
问问题
243 次
3 回答
0
那是因为没有银弹。
您可以在没有先前计算的情况下进行相对较慢的查询，也可以在具有大量先前计算和支持数据结构的情况下进行快速查询。由您来选择。
于 2009-08-11T14:09:55.170 回答
0
听起来您所要求的只是距另一个点一定距离内的点。d(P1, P2) 只是一个数字，因此距 P1 这段距离内的所有点都将满足您的标准。
如果您需要从多个起点多次运行搜索，那么您应该研究标准数据结构，如 kd 树。如果你只执行一次，那么只迭代所有点可能是你最好的选择。
你心目中的应用是什么？
于 2010-01-10T08:47:31.900 回答
0
7年后我想我可以回答我自己的问题：
我正在寻找的图称为单调邻近图 - 最著名的例子是 Delaunay 三角剖分/四面体化。
与空间分区树相比：这样的图提供了更快的查询时间，但需要更多的内存，需要更多的时间，并且由于退化问题，计算可能会失败。
由于它们的这些问题，我认为通常不建议使用它们来加速 KNN 查询，而应该简单地使用 kd-trees。
于 2010-07-23T14:16:37.363 回答