对分治法解决三维最近点对问题的优化

作者：李俊杰; 楼吉林

来源：现代计算机(专业版), 2018, (03): 3-10.

• 三维
• 最近点对

在经典算法中,采用分治法解决三维空间中的最近点对问题,针对该算法进行两点优化:当线段两端点分别处于二分的两个不同空间中时,通过切割长方体(dm*2dm*2dm)多余空间来减少计算次数;在两点进行距离运算时,通过简化距离公式提高两点间距离运算的速度。此优化算法的时间复杂度与经典算法同为O(n*logn),在坐标点有序的情况下能达到O(n),但优化后的算法会使得实际运行速度在线性时间内快于经典算法。

• 单位
  浙江农林大学暨阳学院