3D空间顶点按最大距离d生成无向图边的低复杂度高效算法问询

存在大量时间复杂度低于O(N²)的成熟方案，这类问题属于计算几何领域的固定半径近邻查询问题，在点云处理、3D图形、空间索引领域已经有非常多落地实现：

1. 空间网格划分（栅格法） #

这是固定半径查询场景下首选的轻量方案，原理简单性能极高：

• 将整个3D空间划分为边长等于d的立方体网格，每个顶点只会归属到一个网格中
• 对于任意顶点，仅需要和它所在网格、以及周围相邻的26个3D网格内的顶点做距离校验即可，不需要遍历所有顶点
• 平均时间复杂度为O(N)，仅在所有点都落在同一个网格的极端场景下才会退化到O(N²)，绝大多数点分布均匀的实际场景下性能是暴力法的几十上百倍
• 实现时可以优化距离计算：直接比较平方距离避免开根号开销，即判断(x1-x2)² + (y1-y2)² + (z1-z2)² < d²即可，结果和开根号后比较完全一致

2. k-d树 #

针对多维空间点设计的二叉搜索树：

• 构建树的时间复杂度为O(N log N)，每个点的固定半径查询平均复杂度为O(log N)，整体平均时间复杂度O(N log N)
• 更适合需要多次查询不同半径的场景，单次固定半径查询的性能略低于网格法，但多查询场景下不需要重新划分空间，优势明显

3. 八叉树（Octree） #

专门适配3D空间的树状划分结构：

• 将3D空间递归切分为8个卦限子空间，构建复杂度O(N log N)，固定半径查询平均复杂度O(log N)，整体平均复杂度O(N log N)
• 对3D点分布的适配性更好，是绝大多数3D点云处理库的默认近邻查询方案，比如点云库PCL的半径搜索接口底层默认用八叉树实现

补充说明 #

理论上不存在最坏时间复杂度低于O(N²)的算法：如果所有点对的距离都小于d，你本身就需要输出O(N²)条边，这一步的开销已经决定了最坏复杂度的下界。但只要不是这种极端密集点集的场景，上述所有算法的实际运行效率都远高于暴力遍历。

内容的提问来源于stack exchange，提问作者mTesseracted