欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
象在 1975 一样早， Shamos 和 Hoey 首先给了 O (n lg n )-timedivide-and-conquer 算法(嘘算法在短) 为发现点的最靠近的对的问题。在联合的一个过程，在一些点需要被计算的 3n 之间的欧几里得距离，计算距离的全面复杂性当时因此是 3n lg n。因为距离的计算与另外的基本操作相比是更昂贵的，怎么嘘改善从计算距离的复杂性的方面的算法被考虑。在 1998，周，熊和朱由把这复杂性归结为 2n lg n 改进了 SHalgorithm。在这篇论文，我们做进一步的改进。计算距离的 Theoverall 复杂性被归结为(3n lg n )/2，它仅仅是一半 SHalgorithm 的。
英文摘要：
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.
同期刊论文项目
同项目期刊论文
位置：