使用动态矩形窗求最近点对的几何算法

Geometric algorithm based on dynamic rectangular window for closest-point.

针对几种经典算法的效率问题,提出了一种最近点对求解算法:算法预先找到X、Y坐标轴最大、最小坐标值,将点集按某坐标轴排序,并根据鸽巢原理计算最近点对i间距离的上限,由此上限将整个点集分割成不同的区域,最后在每个区域中通过动态缩小每个点的矩形窗减少了算法的计算次数.通过理论证明和实际验证得出:初始点集有序时算法的时间复杂度为O(n);无序时在一般情况下为O(n),最坏情况下为O(nlogn);算法的时间复杂度和运行时间明显优于经典分治算法和基于底函数的算法.

A closest-point algorithm was proposed for improving to the efficiency of several classical algorithms.First the algorithm found the maximum and minimum values of X and Y axes,secondly sequenced the values in terms of X or Y axis,and thirdly,calculated the ceiling for the distance of closest-point according to the pigeonhole principle.Lastly,the algorithm divided the entire region of input points into several sub-regions by this maximum distance.By dynamically reducing size of a rectangular window of each point in every region,the number of calculations was reduced.Through the theoretical certification and experimental tests the following conclusions can be drawn： the time complexity of algorithm of the initial point set is O（n） when they are orderly distributed,and when they are disordered,the set is O（n） generally,and O（n log n） in the worst case scenario.The algorithm was determined to be obviously better than the divide-conquer and floor-function based algorithms in both complexity and running time.