我目前对生成随机几何图很感兴趣。对于我的特定问题，我们将节点 v 随机放置在单位正方形中，如果它们具有欧几里德距离<= D，则从 v 到节点 u 添加一条边，其中 D=D(u,n) 随 u 和节点数而变化图中的 n。
要点：
计算 D 的成本很高，所以我想尽量减少对该函数的调用次数。
绝大多数情况下，当添加 v 时，边 uv 只会添加到少数节点 u（通常为 0 或 1）。
问题：检查哪些顶点与 v“足够接近”的有效方法是什么？
蛮力算法是计算和比较所有现存节点 u 的 dist(v,u) 和 D(u,n)。这需要 O(n 2 ) 调用 D。
我觉得我们应该能够做得比这更好。也许某种分箱会起作用。我们可以将空间划分为多个 bin，然后对于每个顶点 u，我们存储一个 bin 列表，其中新放置的顶点 v 可能会导致边缘 uv。如果 v 最终被放置在 u 的 bin 列表之外（这应该在大多数情况下发生），那么它太远了，我们不需要计算 D。这有点离题我的头脑建议，我不知道它是否会运作良好（例如，在计算足够接近的垃圾箱时会有开销，这可能太昂贵了），所以我正在寻求反馈。
我可能只会使用分箱方法。
假设我们将单位正方形切成子正方形m x m（当然每个子正方形都有边长1/m）。由于您随机均匀地放置顶点（或者我假设），因此每个正方形n / m^2平均都包含顶点。
根据A1、和A2，您可能可以确定需要检查的最大半径。说小于。然后，在插入 之后，您需要检查它所在的方格，以及所有相邻的方格。无论如何，这是一个恒定数量的正方形，因此对于每次插入，您需要平均检查其他顶点。mnmvO(n / m^2)
我不知道m（如前所述，这取决于A1and A2）的最佳值，但说它会是sqrt(n)，那么您的整个算法可以在O(n)预期的时间内运行。
编辑一个小补充：您可以跟踪具有许多邻居的顶点（因此具有高半径，延伸到多个正方形）并检查它们是否有每个插入的顶点。应该只有少数，所以没问题。
根据您对问题的描述，我会选择R-tree作为您的数据结构。
它通过缩小您需要大幅运行 D 的顶点集来实现非常快速的搜索。然而，在最坏的情况下插入，需要 O(n) 时间。值得庆幸的是，您不太可能使用典型数据集遇到最坏情况的插入。