您是否必须计算所有点的最近邻点，还是仅计算单个点的最近邻点？你必须计算它/它们一次，还是多次？

如果你不能假设你的点，那么空间八叉树可能是你最好的选择，递归地将空间切割成八个相等的立方体，直到每个单元格有少量点。您可以通过检查同一单元格中的所有点并连续爬上树并检查相邻单元格来寻找一个点的邻居。

如果您可以假设最大距离$r_c$其中所有$k$邻居会撒谎，那么您可以使用Cell List，其中包括将空间划分为边长至少为$r_c$在所有维度。然后，任何给定点的邻居将位于该点单元周围的 26 个单元中的任何一个中，因此这些是您需要考虑的唯一候选点。这种方法当然只有在以下情况下才有用$r_c$是合理有界的，如果您试图找到多个点的邻居。

处理边界条件并不是什么额外的困难，因为在这两种情况下，您都在处理可以定期包装的点单元。

更新

如果你只考虑一个目标点，你最好只计算$k$最近的蛮力。

如果你必须计算$k$邻居连续，并且点只移动一点，您可以通过使用Verlet 列表（又名邻居列表）获得一些改进：而不是找到$k$最近的邻居，找到$K>k$最近。如果$r_0$是你的目标点，计算$s = \|r_0-r_K\| - \|r_0-r_k\|$，即与第个和个最近邻居的距离差。$k$$K$

通过这样做，在每次迭代中，您只需重新检查这个最近的邻居并挑选出最近的个。也就是说，直到您的任何点自您第一次寻找个邻居以来移动超过如果发生这种情况，只需重新启动整个过程。$K$$k$$s$$K$

更新 2

您可能已经知道这一点，但如果您的目标是提高效率，您应该尝试使用Median of Medians 算法来找到或个最小点距离。$k$$K$

有一个简单的答案，您只需复制这些点并将其转换为您的加速结构。需要 8 倍以上的内存，但只有真正“解决方案”的代码的 1/8。对于不到 1e7 点左右，这实际上非常合理。

在 scipy.spatial 中有一个很好的 KD-tree 实现，这使得这很容易。

我曾经用它来计算高维空间的 Renyi 停车系数。如果你有兴趣，我可以看看我是否可以挖掘代码。

对于单点查询，没有暴力破解。