%0 Journal Article
%T Engineering the Divide-and-Conquer Closest Pair Algorithm
%A Ming-hui Jiang
%A Joel gillespie
%A <br>Minghui
%A Jiang
%A and
%A Joel
%A Gillespie
%J 计算机科学技术学报
%D 2007
%I 
%X We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem.For n points on the plane,our algorithm keeps the optimal O(n log n)time complexity and,using a circle-packing property,computes at most 7n/2 Euclidean distances,which improves Ge et al.'s bound of(3n log n)/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.
%K algorithmic engineering
%K analysis of algorithms
%K circle packing
%K closest pair
%K computational geometry<br>算法工程
%K 算法分析
%K 计算几何
%K 循环包装
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=CBCDFFE5AEBDB1BF137B1AA0AEC48FCC&yid=A732AF04DDA03BB3&vid=BC12EA701C895178&iid=E158A972A605785F&sid=640CCB6E396307A8&eid=DFBC046213B3DD86&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=19