摘要
文中对Ｐｒｅｐａｒａｔａ和Ｓｈａｍｏｓ在１９８５年提出的求平面点集最近点对的一个分治算法进行了改进，使原来归并时最多需计算３ｎ对点对的距离，改进为最多只需计算２ｎ对点对的距离，计算距离的复杂度在最坏的情况下由原来的３ｎｌｏｇｎ减少到现在的２ｎｌｏｇｎ．
In the paper the divide and conquer algorithm about the closest pair of points on plane set is improved, which was pressented by Preparata and Shamos in 1985. Their algorithm needs at most 3 n calculations on distance, and the time complexity is 3 n log n in worst case. The improved algorithm only needs at most 2 n calculations on distance, and the time complexity of calculation on distance is reduced to 2 n log n .
出处
《计算机研究与发展》
EI
CSCD
北大核心
1998年第10期956-960,共5页
Journal of Computer Research and Development
基金
国家自然科学基金
关键词
最近点对
算法复杂性
计算几何
平面点集
divide and conquer algorithm, the closest pair of points, algorithmic complexity
