在分子动力学模拟中，我们有同样的问题：给定一个截止半径$r_c$, 最多找到其中的所有粒子$r_c$彼此的。最简单的$\mathcal O(n)$方法是将空间划分为边长至少为$r_c$并将每个单元格中的每个粒子与 26 个相邻单元格中的所有粒子进行比较（在三个维度上，对于$d$尺寸，这是$3^d-1$）。通过构造，其他细胞中的粒子将比$r_c$.

在您只测试一组固定点的单个位置的情况下，将空间划分为边长的单元格$\ge r_c$，将点排序到单元格中（可以在$\mathcal O(n)$），然后对于每个试验点，找到该点所在的单元格（可以在$\mathcal O(1)$）并检查到该单元格中的点和周围单元格的距离（可以在$\mathcal O(1)$，这取决于点密度和$r_c$，但不是总点数）。

此处描述了整个过程。如果您想了解更多详细信息，请尝试在谷歌上搜索“单元格链接列表”或“单元格列表”。

kd 树也是一个不错的方法，但是自己实现可能会比较困难（这里似乎有一个 Python 实现，但它不允许添加点）。但是，不要担心树的复杂性，因为对于或多或少均匀的点分布，搜索深度将表现为$\mathcal O(\log_2 n)$为了$n$点。也就是说，点数加倍将使搜索工作量增加一个常数因子。您也只需构建树一次，并且可以在添加新点时快速更新它。

您所说的问题是 Computational Geometry: Range Queries 中的一个经典问题。那是：

输入：n 维欧几里得空间的子集 S，以及该空间 P 中的一组点。
输出：与 S 相交的 P 子集。

《果壳中的算法》一书在第 292 页描述了如何解决类似问题。它描述了矩形区域 S 的算法（不是您的情况下的 n 维球体）。您可以获得一个解决方案，即$O(n^{1-1/d}+r)$，其中n是点数，d是空间的维度，r是查询报告的点数。如果 d 很大，则渐近性能实际上是$O(n)$，这就是通常所说的“维度诅咒”。也就是说，如果维度很高，那么性能会受到很大影响！仍然，$O(n^{1-\frac{1}{d}}+r)$仍然渐近地快于$O(n)$，只是没有我们希望的那么多。

该算法涉及分而治之的策略（递归）和特殊的数据结构（kd-tree）。下面是算法的概要：

Begin MainProgram

    results = a new SET   (a kd-tree)
    search(space,root,results)
    return results
endMainProgram

Subroutine search(space,node,results)
    if (space contains node.region) then
        add node.point to the results
        for each descendant of node
            add d.point to results
        return
    if (space contains node.point) then 
        add node.point to results
    if (space extends below node.coordinate) then
        search(space,node.below,results)
    if (space extends above node.coordinate) then
        search(space,node.above,results)
endsubroutine

-来源：算法概述，第 298 页

矩形情况的关键是我们可以轻松定义数据结构，以便我们可以一次包含整个子集......因此是 KD-tree。KD 树只是通过用超平面连续切割它来分割你的 n 维空间，这与 3D 空间可以被平面分割的方式非常相似。

对于涉及径向范围查询（不是矩形框）的特定问题，您可能能够找到类似的基于 n 球体的递归空间分割......有一个类似的数据结构称为vp-tree设计用于在超球面坐标中实现空间分割。你可能想看看

">此出版物了解有关 vp-trees 理论的更多详细信息。

当然，如果您的目标真的是使用算法作为进行科学的工具，那么编码可能会很麻烦。在这种情况下，我建议您研究已经实现了您可以使用的这些数据结构的库。在这种情况下，计算几何库将非常有用。CGAL库有用于 d 维范围搜索的子程序，您可能会感兴趣 。这是另一个具有范围查询子例程的库列表。

或者，如果您可以获取正在搜索的球面范围内的大部分点（但不是全部），您可能需要考虑使用本文中的近似算法。