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

求解最近点对问题在诸如地理信息查询、空间数据库等领域应用广泛。但到目前为止,还没有一种高效的求解算法,如传统求解最近对的分治算法存在比较次数较多、阈值收敛速度慢、计算距离次数较多的缺点。基于网格技术的求解最近邻方法存在网格的大小难以确定和算法效率低的问题。据此,首先提出基于单向检测的最近对求解算法(cp_sdd),然后提出按行划分的排序算法(rds),最后得到基于分行排序单向检测的最近对求解算法(cp_sdd+rds)。该算法不仅克服了分治法存在的缺点,而且子算法(rds)的分行思想还克服了划分网格过程中存在的弊端。大量实验表明,cp_sdd+rds算法是高效和可行的。