首页 | 本学科首页   官方微博 | 高级检索  
     

An Improved Algorithm for Finding the Closest Pair of Points
作者姓名:Qi Ge  Hai-Tao Wang  and Hong Zhu
作者单位:Department of Computer Science and Engineering, Fudan University, Shanghai 200433, P.R. China
基金项目:This work is supported by the National Natural Science Foundation of China (Grant No. 60496321) and Shanghai Science and Technology Development Fund (Grant No. 025115032).
摘    要:As early as in 1975, Shamos and Hoey first gave an O(n lg n)-time divide-and-conquer algorithm (Stt algorithm in short) for the problem of finding the closest pair of points. In one process of combination, the Euclidean distances between 3n pairs of points need to be computed, so the overall complexity of computing distance is then 3n lgn. Since the computation of distance is more costly compared with other basic operation, how to improve SH algorithm from the aspect of complexity of computing distance is considered. In 1998, Zhou, Xiong and Zhu improved SH algorithm by reducing this complexity to 2n lg n. In this paper, we make further improvement. The overall complexity of computing distances is reduced to (3n lg n)/2, which is only half that of SH algorithm.

关 键 词:Hoey算法  复杂性  基础运算  逼近点
收稿时间:2005-03-26
修稿时间:2005-03-262005-08-22

An Improved Algorithm for Finding the Closest Pair of Points
Qi Ge,Hai-Tao Wang,and Hong Zhu.An Improved Algorithm for Finding the Closest Pair of Points[J].Journal of Computer Science and Technology,2006,21(1):27-31.
Authors:Qi Ge  Hai-Tao Wang  Hong Zhu
Affiliation:(1) Department of Computer Science and Engineering, Fudan University, Shanghai, 200433, P.R. China
Abstract:As early as in 1975, Shamos and Hoey first gave an O(n Ig n)-time divide-and-conquer algorithm (SH algorithm in short) for the problem of finding the closest pair of points. In one process of combination, the Euclidean distances between 3n pairs of points need to be computed, so the overall complexity of computing distance is then 3n lg n. Since the computation of distance is more costly compared with other basic operation, how to improve SH algorithm from the aspect of complexity of computing distance is considered. In 1998, Zhou, Xiong and Zhu improved SH algorithm by reducing this complexity to 2n lg n. In this paper, we make further improvement. The overall complexity of computing distances is reduced to (3n lg n)/2, which is only half that of SH algorithm.
Keywords:Shamos and Hoey algorithm  divide and conquer  closest pair of points  complexity
本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录!
点击此处可从《计算机科学技术学报》浏览原始摘要信息
点击此处可从《计算机科学技术学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号