摘要：针对平面上最接近点对问题,分别考虑其在离线环境和在线环境下的两种情况。在离线环境下,针对分治算法,结合点集本身的稀疏性质和圆的性质,给出一个改进的合并算法,使得在合并过程中由每个点的最多6次计算距离降为4次运算,从而提高算法的效率。在在线环境下,给出3种算法求解此问题。第1种算法是每给出第k个点就计算k-1次。第2种算法是给出一个判别式子,在给第k个点时,首先对前k-1个点进行判断,判断出与之会影响当前最小距离的点后再进行计算。第3种算法是结合几何知识,证明得到在此问题中,当新的点出现时,最多只会有6个点与之影响当前最小距离,所以通过插序找出此6点再进行计算。可以证明这3种算法的时间复杂度均为O（n2）,但显然随着点数n的增大,算法的平均时间复杂度一定会依次降低。

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社