我正在寻找数据结构。假设您有n个点p：=（x，y），其中x，y∈[-128，128]现在，您启动数据结构并将所有n个点添加到其中。现在，对于任何点，您都希望轻松找到靠近它的任何点。更确切地说：指定半径r <1并指向p。您需要一个函数F，该函数输出d（p，q） 在最坏的情况下，实际上没有改进的余地，因此我们假设在每个点p的每个间隔中，所有点的至少50％不在函数F指定的半径范围内上面的值是任意的，应该可以与任何其他数字互换。我选择这些数字是为了使问题更容易理解，而且x和y是浮点数。 我想要一个答案，使我指向另一篇文章，维基百科条目或任何其他具有相同或相似问题的来源。我真的希望没人会整天试图向我解释数据结构;）无论如何，我们感谢所有帮助。非常感谢。
您可以使用许多好的数据结构来有效地二维解决问题。与标准线性搜索相比，k-d树数据结构允许您相当快地搜索矩形中的所有点，前提是这些点或多或少是随机分布的。四叉树数据结构类似地支持这种搜索。 R树是另一种选择，尽管它们主要针对有大量点并希望有效地将信息存储在磁盘上的情况进行了优化。
我的回忆是，在最坏的情况下，所有这些方法都需要时间O（n），但仅在经过病理选择的情况下才能使用。对于具有“合理”分布的输入，这些算法的运行时间通常要好得多，因此得到了广泛的应用。
希望这会有所帮助！
这个问题让我想起了我前一段时间写的粒子模拟（有类似的问题，就像您描述的那样）。我发现了一个数据结构，该结构允许（在实践中有一些小偏差，并假设您选择了很多块）以提高O（n）的复杂度。