使用动态矩形窗求最近点对的几何算法
姜春茂;张国印
【期刊名称】《哈尔滨工程大学学报》 【年(卷),期】2013(034)003
【摘要】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 0(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.%针对几种经典算法的效率问题,提出了一种最近点对求解算法:算法预先找到X、y坐标轴最大、最小坐标值,将点集按某坐标轴排序,并根据鸽巢原理计算最近点对i间距离的上限,由此上限将整个点集分割成不同的区域,最后在每个区域中通过动态
使用动态矩形窗求最近点对的几何算法
