论文部分内容阅读
摘要：描述了平面最接近点对问题，针对这一问题给出了3种算法，循环遍历算法、分治算法和平面扫描算法，并详细分析了3种算法的时间复杂度。
关键词：平面最接近点对；循环遍历算法；分治算法；平面扫描算法
中图法分类号：TP391文献标识码：A文章编号：1009-3044(2007)15-30828-01
Algorithms for Finding the Closest Pair of Points
WU Zhong-bo
(Department of Electrical and Information Engineering, Xiangfan University, Xiangfan 441053, China)
Abstract: In this paper we describe the problem of finding the closet pairs of points in the plane and we use three algorithms to solve this problem including na?ve algorithm, divide and conquer algorithm and plane sweep algorithm. At last we analyze the efficiency of these algorithms.
Key words: closest Pair of Points; divide-and-conquer algorithm; circulation Algorithm; plane sweep algorithm
1 引言
在计算机应用中，常用点、圆等简单的几何对象表达现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其领域中其他几何对象的信息。最接近点对问题常用于空中交通的计算机自动控制系统中，也是计算机几何学研究的基本问题之一。
该问题可以描述为：设S是平面上n个点的集合（n>=2），对于S中的每一个点p∈S，都有2个坐标值p(x)和p(y)，找出其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。
2 算法描述
2.1 循环遍历算法
循环遍历算法是最简单的解决办法，算法思想如下：依次计算两个节点之间的距离，然后进行比较，从中选择出具有最短距离的点对即可。
首先对于n个点有n*(n-1)个点对，所以依次计算两个节点之间距离的时间复杂度为O(n2)；然后需要将n*(n-1)个点对扫描一遍以选择出最短距离的点对，时间复杂度也为O(n2)。所以，循环遍历算法的时间复杂度为O(n2)。
2.2分治算法
用分治算法求S中最接近点对的基本思想是：选取一垂直线L∶x = m作为分割直线，将S的点分割为点数大致相同的2个子集S1和S2，使得：
S1={p∈S | p(x)≤m}，S2={p∈S | p(x)>m}
其中：m是S中各点x坐标的中位数，因此S1和S2中点数大致相同，且S=S1∪S2。递归地在S1和S2上解最接近点对的问题，分别得到S1和S2中的最小距离d1和d2，并设d=min{d1,d2}。用P1和P2分别表示在直线L左边和右边与其距离在d范围的点构成的两个垂直长条平面区域。
P1：{p∈P1 | (|m-x(p)|≤d)}，P2：{p∈ P2 | (|x(p)-m|≤d)}
S中的最接近点对的距离或者是d，或者是某个{p,q}点对的距离，其中p∈P1，q∈P2。如果{p,q}是S中的最接近点对，则必有distance(p,q) 将上述描述简化如下：
图1 分治算法
（1）递归用L将节点集分成两个相等的部分；
（2）设d是d1和d2的最小值；
（3）删除离L超过d的节点；
（4）按照y维扫描剩下的节点，计算5个邻居的距离；
（5）如果距离小于d，更新d
下面我们分析分治算法的时间复杂度，由于步骤2-5是每个递归过程中都要去做的，我们先分析2-5。步骤2时间复杂度为O(1)；步骤3时间复杂度为O(n)；步骤4时间复杂度为O(1)；步骤5时间复杂度为O(1)，所以步骤2-5的时间复杂度为O(n)。步骤1递归地将平面S中的点分成两个相等的部分时间复杂度为O(logn)，所以总的时间复杂度为O(n)* O(logn)=O(nlogn)。
2.3 平面扫描算法
平面扫描算法如图2所示，用一根垂直的线从左扫到右。在扫描的过程中，需要维护遇到的最近的节点对以及它们之间的距离d；还需要维护一个区域D，D是一个矩形，右边界由下一个扫描到的点p确定，宽为已经扫描的点中的最近点对的距离。每次遇到下一个点p，我们就执行以下操作：
（1）将在x轴上离p的距离超过d的节点从D中删除掉；
（2）确定p左边离p最近的点q；
（3）如果q点和p之间的距离小于d，更新最近的节点对和d；
下面我们分析平面算法的时间复杂度。首先对所有点按x坐标排序，时间复杂度为O(nlogn)；其次在D中插入删除点，每次插入的时间复杂度为O(logn)，因为共有n个点，所以时间复杂度为O(nlogn)；然后比较p点的常数个邻居，时间复杂度为O(n)。所以平面扫描算法的时间复杂度为O(nlogn)。
3 结束语
本文描述了平面最接近点对问题，针对这一问题给出了3种算法，分别是循环遍历算法、分治算法和平面扫描算法，其中循环遍历算法的时间复杂度为O(n2)，分治算法和平面扫描算法的时间复杂度都为O(nlogn)。
参考文献：
[1]林志庆,范庆. 平面最接近点对问题的改进算法[J]. 福州大学学报, 1999,12: 19-23.
[2]Bentely J L, Shamos M I. Divide and conquer in multidimensional space [A]. Proc 8th ACM Annual Symp on Theory of Computer [C], 1976: 220-230.
[3]王晓东. 算法设计与分析[M]. 北京:清华大学出版社, 2002.
关键词：平面最接近点对；循环遍历算法；分治算法；平面扫描算法
中图法分类号：TP391文献标识码：A文章编号：1009-3044(2007)15-30828-01
Algorithms for Finding the Closest Pair of Points
WU Zhong-bo
(Department of Electrical and Information Engineering, Xiangfan University, Xiangfan 441053, China)
Abstract: In this paper we describe the problem of finding the closet pairs of points in the plane and we use three algorithms to solve this problem including na?ve algorithm, divide and conquer algorithm and plane sweep algorithm. At last we analyze the efficiency of these algorithms.
Key words: closest Pair of Points; divide-and-conquer algorithm; circulation Algorithm; plane sweep algorithm
1 引言
在计算机应用中，常用点、圆等简单的几何对象表达现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其领域中其他几何对象的信息。最接近点对问题常用于空中交通的计算机自动控制系统中，也是计算机几何学研究的基本问题之一。
该问题可以描述为：设S是平面上n个点的集合（n>=2），对于S中的每一个点p∈S，都有2个坐标值p(x)和p(y)，找出其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。
2 算法描述
2.1 循环遍历算法
循环遍历算法是最简单的解决办法，算法思想如下：依次计算两个节点之间的距离，然后进行比较，从中选择出具有最短距离的点对即可。
首先对于n个点有n*(n-1)个点对，所以依次计算两个节点之间距离的时间复杂度为O(n2)；然后需要将n*(n-1)个点对扫描一遍以选择出最短距离的点对，时间复杂度也为O(n2)。所以，循环遍历算法的时间复杂度为O(n2)。
2.2分治算法
用分治算法求S中最接近点对的基本思想是：选取一垂直线L∶x = m作为分割直线，将S的点分割为点数大致相同的2个子集S1和S2，使得：
S1={p∈S | p(x)≤m}，S2={p∈S | p(x)>m}
其中：m是S中各点x坐标的中位数，因此S1和S2中点数大致相同，且S=S1∪S2。递归地在S1和S2上解最接近点对的问题，分别得到S1和S2中的最小距离d1和d2，并设d=min{d1,d2}。用P1和P2分别表示在直线L左边和右边与其距离在d范围的点构成的两个垂直长条平面区域。
P1：{p∈P1 | (|m-x(p)|≤d)}，P2：{p∈ P2 | (|x(p)-m|≤d)}
S中的最接近点对的距离或者是d，或者是某个{p,q}点对的距离，其中p∈P1，q∈P2。如果{p,q}是S中的最接近点对，则必有distance(p,q)
图1 分治算法
（1）递归用L将节点集分成两个相等的部分；
（2）设d是d1和d2的最小值；
（3）删除离L超过d的节点；
（4）按照y维扫描剩下的节点，计算5个邻居的距离；
（5）如果距离小于d，更新d
下面我们分析分治算法的时间复杂度，由于步骤2-5是每个递归过程中都要去做的，我们先分析2-5。步骤2时间复杂度为O(1)；步骤3时间复杂度为O(n)；步骤4时间复杂度为O(1)；步骤5时间复杂度为O(1)，所以步骤2-5的时间复杂度为O(n)。步骤1递归地将平面S中的点分成两个相等的部分时间复杂度为O(logn)，所以总的时间复杂度为O(n)* O(logn)=O(nlogn)。
2.3 平面扫描算法
平面扫描算法如图2所示，用一根垂直的线从左扫到右。在扫描的过程中，需要维护遇到的最近的节点对以及它们之间的距离d；还需要维护一个区域D，D是一个矩形，右边界由下一个扫描到的点p确定，宽为已经扫描的点中的最近点对的距离。每次遇到下一个点p，我们就执行以下操作：
（1）将在x轴上离p的距离超过d的节点从D中删除掉；
（2）确定p左边离p最近的点q；
（3）如果q点和p之间的距离小于d，更新最近的节点对和d；
下面我们分析平面算法的时间复杂度。首先对所有点按x坐标排序，时间复杂度为O(nlogn)；其次在D中插入删除点，每次插入的时间复杂度为O(logn)，因为共有n个点，所以时间复杂度为O(nlogn)；然后比较p点的常数个邻居，时间复杂度为O(n)。所以平面扫描算法的时间复杂度为O(nlogn)。
3 结束语
本文描述了平面最接近点对问题，针对这一问题给出了3种算法，分别是循环遍历算法、分治算法和平面扫描算法，其中循环遍历算法的时间复杂度为O(n2)，分治算法和平面扫描算法的时间复杂度都为O(nlogn)。
参考文献：
[1]林志庆,范庆. 平面最接近点对问题的改进算法[J]. 福州大学学报, 1999,12: 19-23.
[2]Bentely J L, Shamos M I. Divide and conquer in multidimensional space [A]. Proc 8th ACM Annual Symp on Theory of Computer [C], 1976: 220-230.
[3]王晓东. 算法设计与分析[M]. 北京:清华大学出版社, 2002.