如何高效计算两组3D点集间的最小距离？

针对两组3D坐标点集A、B的最近点对问题（即找到a∈A、b∈B使得两点距离最小），目前已知的最高效解决方案主要分为以下几类，时间复杂度可达到接近O((m+n) log(m+n))（m、n分别为A、B的点数）：

1. 分治算法的3D扩展 #

平面场景的分治思路可以直接扩展到3D空间，核心步骤如下：

• 排序分割：将A∪B的所有点按x坐标排序，递归将点集划分为左右两部分。
• 递归求解：分别计算左半区、右半区的跨集最小距离，取两者较小值作为当前的d_min。
• 边界区域处理：收集所有距离分割平面小于d_min的点，按y坐标排序后，对每个点仅检查其y、z坐标均在d_min范围内的点，计算跨集距离并更新d_min。
  该方法理论时间复杂度与平面分治一致，但3D场景下边界区域的检查次数更多，实际常数稍大，仍是理论级高效方案。

2. 空间索引结构优化 #

针对大规模点集，空间索引能大幅减少需计算的点对数量，常用结构包括：

• k-d树：先构建包含所有点的k-d树，再对A中每个点，在树中查询B里的最近邻点，全程记录最小距离。k-d树构建时间为O((m+n) log(m+n))，单个点的最近邻查询平均时间为O(log(m+n))，整体复杂度接近O((m+n) log(m+n))。
• 范围树：基于分治构建多层索引，支持高效范围查询，适合批量处理点的最近邻搜索。

3. 哈希网格（Grid Hashing） #

对于分布相对均匀的点集，这是实用性极强的高效方案：

• 网格划分：根据初始估计的最小距离（或动态调整的网格大小），将3D空间划分为边长为d的立方体网格。
• 点映射：将A、B中的点分别映射到对应的网格单元中。
• 邻域检查：对每个A中的点，仅检查其所在网格及相邻的26个网格内的B点，计算距离并更新最小距离。
  该方法平均时间复杂度接近O(m+n)，但最坏情况可能退化为O(mn)，适合点分布均匀的场景，实现也相对简单。

关键注意事项 #

• 区分单集最近点对与跨集最近点对：前者是找同一集合内的最近点，后者是两个集合间的最近点，分治、索引结构的实现细节会有差异。
• 距离计算优化：为避免开平方的性能开销，可先比较距离的平方，仅在确认需要更新最小距离时再计算实际距离。

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