| 求平面点集最近点对的一个改进算法 |
| |
| 引用本文： | 周玉林 熊鹏荣. 求平面点集最近点对的一个改进算法[J]. 计算机研究与发展, 1998, 35(10): 956-960 |
| |
| 作者姓名： | 周玉林 熊鹏荣 |
| |
| 作者单位： | [1]上饶师范专科学校数学系 [2]复旦大学计算机科学系 |
| |
| 摘 要： | 文中对Ｐｒｅｐａｒａｔａ和Ｓｈａｍｏｓ在１９８５年提出的求平面点集最近点对的一个分治算法进行了改进，使原来 归并时最多需计处３ｎ对点对的距离，改进的为最多只需计算２ｎ
|
| 关 键 词： | 最近点对 算法复杂性 计算几何 平面点集 |
AN IMPROVED ALGORITHM ABOUT THE CLOSEST PAIR OF POINTS ON PLANE SET |
| |
| Zhou Yulin,Xiong Pengrong,and Zhu Hong. AN IMPROVED ALGORITHM ABOUT THE CLOSEST PAIR OF POINTS ON PLANE SET[J]. Journal of Computer Research and Development, 1998, 35(10): 956-960 |
| |
| Authors: | Zhou Yulin Xiong Pengrong and Zhu Hong |
| |
| Affiliation: | Zhou Yulin,Xiong Pengrong,and Zhu Hong * |
| |
| Abstract: | 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 . |
| |
| Keywords: | divide and conquer algorithm the closest pair of points algorithmic complexity |
| 本文献已被 CNKI 维普 等数据库收录！ |
