|
|||||
|
|
| 平面上最接近点对问题的研究 | |
| 作者单位： | ;1.河南理工大学数学与信息科学学院 |
| 摘 要： | 针对平面上最接近点对问题,分别考虑其在离线环境和在线环境下的两种情况。在离线环境下,针对分治算法,结合点集本身的稀疏性质和圆的性质,给出一个改进的合并算法,使得在合并过程中由每个点的最多6次计算距离降为4次运算,从而提高算法的效率。在在线环境下,给出3种算法求解此问题。第1种算法是每给出第k个点就计算k-1次。第2种算法是给出一个判别式子,在给第k个点时,首先对前k-1个点进行判断,判断出与之会影响当前最小距离的点后再进行计算。第3种算法是结合几何知识,证明得到在此问题中,当新的点出现时,最多只会有6个点与之影响当前最小距离,所以通过插序找出此6点再进行计算。可以证明这3种算法的时间复杂度均为O(n2),但显然随着点数n的增大,算法的平均时间复杂度一定会依次降低。 |
| 关 键 词： | 最接近点对 分治算法 极坐标系 插序 |
The Study of Closest Point Pairs in Plane |
|
| Abstract: | |
| Keywords: | |