分治法实现最接近点对问题的三维推广算法

The Algorithm of Finding Pair of Three-Dimensional Points with the Minimum Distance by Means of Divide and Conquer

最接近点对问题是空中交通控制系统应用中的一个重点问题,也是计算机几何学研究的基本问题之一.利用分治法已经解决该问题的一维和二维情况,且算法都可以在O(n*logn)时间内完成.本文在原有一维和二维算法基础上,提出了利用分治法实现该问题的三维情况的算法,并对算法的效率进行了分析.

Finding pair of dimensional points with the minimum distance is the key problem in the application of the air traffic control system and it is also a basic one of the computerized geometry study. By means of divide and conquer, the problem has been solved from the point of linearity and space, furthermore, it can be accomplished within the 0 （ n ＊ logn）. Under the base of unidimensional and two - dimensional algorithm, this paper put forward an three-dimensional algorithm by means of divide and conquer and analyzed the efficiency of the algorithms.