我正在寻找数据结构。 在最坏的情况下，确实没有改进的余地，因此我们假设在每个点p的每个间隔中，至少有50％的点不在函数F指定的半径范围内
假设您有n个点p：=（x，y），其中x，y∈[-128，128]
现在，您启动数据结构并将所有n个点添加到其中。
现在，对于任何点，您都希望轻松找到靠近它的任何点。
更准确地说：
指定半径r
您需要一个函数F，该函数输出d（p，q）
我很乐意回答:)
对于了解自己的东西并希望进一步提供帮助的人们：
假设点在间隔内移动（最大距离为
在每个时间点（n次）调用每个时间间隔F的过程中，我们现在要扩展优化，即在每个时间间隔之后，函数F的效率同样有效。
因此，我们需要一个利用数据结构的函数G。
G叫一次，F叫n次。我们想要O（G）+ n * O（F）
上面的值是任意的，应该可以与任何其他数字互换。我选择这些数字是为了使问题更容易理解，而且x和y是浮点数。
我想要一个答案，使我指向另一篇文章，维基百科条目或任何其他具有相同或相似问题的来源。我真的希望没人会整天试图向我解释数据结构;）
无论如何，我们感谢所有帮助。非常感谢。
是否有一个数据结构可以有效地找到彼此靠近的点？
•
问答
hlpapple 回答：是否有一个数据结构可以有效地找到彼此靠近的点？
这个问题让我想起了我前一段时间写的粒子模拟（它有类似的问题，就像你描述的那样）。我发现了一个数据结构，该结构允许（实际上有一些小偏差，并假设您选择了很多块）以提高O（n）的复杂性。
您可以将二维空间划分为较小的矩形（我认为正方形是您的情况中最好的）块（边长大于r）。
然后，您需要O(n)时间将这些点分类为这些块。
让k是您拥有的块总数。
然后找到每个点在半径r内的所有点将取O(n*(n/k)) = O(n²/k)，其中n / k是每个块内点的近似数目（假设有正则分布粒子模拟，虽然不确定您的问题）。请记住，您还需要查看每个相邻的8个块！
然后，您还有一个额外的O(k)，这是由于您需要遍历大块来访问元素。
因此，总体而言，此数据结构的复杂度为O(n²/k + n + k)。
现在要找到n和最优k之间的关系，您必须找到函数f(k) = a*n²/k + b*n + c*k的最小值，这可以通过找到导数并将其设置为零来完成： / p>
f'(k) = -an²/k² + c = 0→n²/k² = c/a = constant→n与k成正比，因此是否可以将k选择为最佳值：
O(n²/k + n + k) = O(n²/n + n+ n) = O(n)
当O(n²)
k = 1
,
有许多好的数据结构可用于有效地从二维角度解决问题。与标准线性搜索相比，k-d树数据结构允许您相当快地搜索矩形中的所有点，前提是这些点或多或少是随机分布的。四叉树数据结构类似地支持这种搜索。 R树是另一种选择，尽管它们主要针对有大量点并希望有效地将信息存储在磁盘上的情况进行了优化。
我的回忆是，在最坏的情况下，所有这些方法都需要时间O（n），但仅在病理选择的输入下。对于具有“合理”分布的输入，这些算法的运行时间通常要好得多，因此得到了广泛的应用。
希望这会有所帮助！