文档介绍：第八章数论算法及计算几何算法
1
精选ppt
凸包问题
1、问题提出
给定一个点集S＝{P0,P1,…,Pn-1}，它的凸包是一个最小的凸多边形P，且满足S中的每个点或者在P的边界上或者在P的内部。
如果点集两个集合S1和S2。
7
精选ppt
子集S1的凸包由线段P0Pn-1作为下边界、多节链条作为上边界组成。这条上边界称为上包。
子集S2的凸包由线段P0Pn-1作为上边界、多节链条作为下边界组成。这条下边界称为下包。
整个集合的凸包由上包和下包构成。如图8-2所示。
8
精选ppt
2、算法求解步骤
构造上包步骤：
找到子集S1中的点Pmax，它是距离线段P0Pn-1最远的点
连接，找出S1中位于直线左边的点，这些点构成集合S11；找出S1中位于直线左边的点，这些点构成集合S12；△P0PmaxPn-1内部的点不予考虑。
递归构造S11和S12的上包，然后简单地将它们连接起来，得到S1的上包。
构造下包步骤：
找到子集S2中的点Pmin，它是距离线段P0Pn-1最远的点
连接，找出S2中位于直线右边的点，这些点构成集合S21；找出S2中位于直线右边的点，这些点构成集合S22；△P0PminPn-1内部的点不予考虑
递归构造S21和S22的下包，然后简单地将它们连接起来，得到S2的下包。
9
精选ppt
3、算法程序语言描述

详见课本
10
精选ppt

1、问题提出
最接近点对问题要求给定平面上n个点组成的集合S，找出其中n个点组成的点对中距离最近的一对点。
该问题具有很大的实际应用价值，例如，一个控制空中或者海上交通的系统就需要了解2个最近的交通工具，以预测可能产生的相撞事故。
2、解决问题方法
穷举搜索、分治法（略）
11
精选ppt

1、算法思想
分别计算点集中每一对点的距离Dij，从中找出值最小的那对点。
为了避免点对的重复计算，算法只考虑i<j的情况.
2、算法描述
Double shortdis( )
{double temp=∞,d=0;
for(int i=0; i<n-1;i++ )
for(int j=i+1; j<n,j++ )
d=sqrt( (pow( p[i].x-p[j].x)) , 2)+pow((p[i].y-p[j].y),2 );
if(d<tempt)
{tempt=d; p1=p[i]; p2=p[j]; }
}
12
精选ppt
3、算法分析
从算法描述可知循环体内的时间是常数时间，循环次数，
因此算法的时间复杂性为O(n2) 。
13
精选ppt

1、算法思想
将所给平面上的n个点的集合S分成规模大致相等的两个子集S1和S2。递归求解S1和S2中的最接近点对；
集合S中的最接近点对：
或者是子问题S1的解；
或者是子问题S2的解，
或者是一个点在S1中，一个点在S2中的情况组成的最接近点对。
14
精选ppt
一维情形下最小点对：
算法描述：
Step1：用xm将x1,x2,…,xn分成两部分S1和S2
Step2：递归求S1中最接近点对，其距离为d1；
Step3：递归求S2中最接近点对，其距离为d2；
Step4：求S1中的最大值p，S2中的最小值q；
Step5：计算d3=|p-q|；
Step6：比较d1,d2,d3确定哪个是最接近点对。
算法分析
解此递归方程可得T(n)=O(nlogn)。
15
精选ppt
二维情形
算法描述：
Step1：选取一垂直线l：x=xm作为分割线。其中xm为S中各点x坐标的中位数。由此将S分割为S1和S2
Step2：递归求S1中最接近点对，其距离为d1
Step3：递归求S2中最接近点对，其距离为d2
Step4：令d=min(d1,d2)
Step5：找出S1中的某个点p和S2中的某个点q组成的点对(p,q) （难点）
Step6：比较|p-q|,d1,d2确定哪个是最接近点对
思考：如何找出点对(p,q) ？
如果|p-q|小于d，则p点分布在P1带形区域内(左虚线和分割线l所夹的区域)，q点分布在P2带形区域内(右虚线和分割线l所夹的区域)。如