CP_SDD+RDS:基于分行排序单向检测求解最近对  

CP_SDD+RDS:An Algorithm Based on Row-divided Sorting and Single-direction Detecting for Finding Closest Pair of Points

作　　者：姚华传[1] 王丽珍[1] 陈红梅[1] 胡新[1] 

机构地区：[1]云南大学信息学院计算机科学与工程系,昆明650091

出　　处：《计算机科学》2013年第7期201-205,共5页Computer Science

基　　金：国家基金项目(61063008;61272126;61262069);云南省应用基础研究基金项目(2010CD025);云南省教育厅基金项目(2012C103)资助

摘　　要：求解最近点对问题在诸如地理信息查询、空间数据库等领域应用广泛。但到目前为止,还没有一种高效的求解算法,如传统求解最近对的分治算法存在比较次数较多、阈值收敛速度慢、计算距离次数较多的缺点。基于网格技术的求解最近邻方法存在网格的大小难以确定和算法效率低的问题。据此,首先提出基于单向检测的最近对求解算法(CP_SDD),然后提出按行划分的排序算法(RDS),最后得到基于分行排序单向检测的最近对求解算法(CP_SDD+RDS)。该算法不仅克服了分治法存在的缺点,而且子算法(RDS)的分行思想还克服了划分网格过程中存在的弊端。大量实验表明,CP_SDD+RDS算法是高效和可行的。Finding out the closest pair of points has been widely applied in many areas,such as the geographic informa- tion query system and spatial databases etc. But so far, there is not an efficient algorithm for the problem. For example, the divide and conquer algorithm contains much comparison, slow convergence and much computing of the distance be- tween two points. Grid-based methods used to solve the nearest neighbor problem can not determine the size of the grid reasonably, and they are inefficient. For this reason, a single-direction detecting algorithm （CP_SDD） was presented in the paper. Then a row-divided sorting algorithm was proposed. Finally, an algorithm based on row-divided sorting and single-direction detecting for finding the closest pair of points （CP_SDD＋RDS） was formed. Compared with the divide and conquer algorithm, our algorithm not only efficiently overcomes these drawbacks that occur in the divide and con- quer algorithm, the row-divided strategy of the RDS algorithm is also effective to solve these problems that occur in grid-based methods. A large number of experiments show that the CP_SDD＋RDS algorithm is efficient and feasible.

关 键 词：最近对 直角距离 模糊距离 点密度 点密集区 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]