我目前对生成随机几何图形很感兴趣。对于我的特定问题，我们将节点 v 随机放置在单位正方形中，如果节点 u 具有 Euclidean distance，则添加一条从 v 到节点 u 的边。 <= D，其中 D=D(u,n) 随图中的 u 和节点数 n 而变化。
要点:
计算 D 的成本很高，所以我想尽量减少对此函数的调用次数。
绝大多数情况下，当添加 v 时，边 uv 只会添加到少数节点 u(通常为 0 或 1)。
Question: What is an efficient method for checking which vertices u are "close enough" to v?
蛮力算法是计算和比较所有现存节点u的dist(v,u)和D(u,n)。这需要对 D 进行 O(n2) 次调用。
我觉得我们应该能够做得比这更好。也许某种装箱会起作用。我们可以将空间划分为 bins，然后对于每个顶点 u，我们存储一个 bins 列表，新放置的顶点 v 可以在其中产生边 uv。如果 v 最终被放置在 u 的 bins 列表之外(大多数情况下应该发生)，那么它就太远了，我们不需要计算 D。这有点离题了-我的建议，我不知道它是否有效(例如，计算足够近的箱子会产生开销，这可能成本太高)，所以我正在寻求反馈。
最佳答案
根据您对问题的描述，我会选择 R-tree作为您的数据结构。
它通过缩小运行 D 所需的顶点集来实现非常快速的搜索。然而，在最坏情况下插入，需要 O(n) 时间。值得庆幸的是，您不太可能在典型数据集上遇到最坏情况的插入。
关于algorithm - 有效地检查大量节点中哪些节点靠得很近？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18948028/