%0 Journal Article
%T An Improved Algorithm for Finding the Closest Pair of Points
%A Qi Ge
%A Hai-Tao Wang
%A Hong Zhu
%A <br>Qi Ge
%A Hai-Tao Wang
%A and Hong Zhu
%J 计算机科学技术学报
%D 2006
%I 
%X 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.
%K Shamos and Hoey algorithm
%K divide and conquer
%K closest pair of points
%K complexity<br>Hoey算法
%K 复杂性
%K 基础运算
%K 逼近点
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=406F073E0D655F9E1952AD539B91C517&yid=37904DC365DD7266&vid=659D3B06EBF534A7&iid=CA4FD0336C81A37A&sid=DB817633AA4F79B9&eid=4AD960B5AD2D111A&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=1&reference_num=5