空间最近点对的计算机算法研究

The Computer Algorithms of Finding Shortest Distance Pair of Points in Space

最近点对问题是空中交通控制系统中的一个重要问题,并且在许多领域都有应用,也是计算几何学研究的基本问题之一。利用分治法解决该问题的线性和平面情况,算法可以在O(n*logn)时间内完成。本文在此基础上,进一步实现空间最接近点的算法,并对算法的复杂性进行分析。

Finding Shortest Distance pair of points in space is the important problem of the air traffic control system. There are a lot of applications with the problem and it is also a basic one of the computing geometry study. By methods of divide and conquer, the problem has been solved from the points of linearity and plane, it can be accomplished within the O（n ＊ logn） time. Under the base of unidimentional and two-dimensional algorithm, this paper solves the Shortest Distance pair of points in space problem and analyzes the complexity of the algorithms.