第八章 数论算法及计算几何算法 239
4.算法分析
由算法描述可以发现,点集中的点构成的线段数目最多为n(n-1)/2,对每一条线段,最坏情况要检查点集中其余n-2个点属于哪个半平面,故算法的时间复杂性为O(n3)。
8.5.2 凸包问题的分治法
解决凸包问题的分治法不止一种,这里只讲最简单的。该算法有时也称为快包,因为它的操作和快速排序十分相似。
1.算法思想
将点集S中的点按照x坐标升序排序,x坐标相同的按照y坐标升序排序,排好序的序列存放在点结构数组P中。那么最左边的点P0、最右边的点Pn-1肯定是凸包上的点。线段P0Pn-1将集合S中的点分成两个集合S1和S2。子集S1的凸包由线段P0Pn-1作为下边界、多节链条作为上边界组成。这条上边界称为上包。类似的,子集S2的凸包由线段P0Pn-1作为上边界、多节链条作为下边界组成。这条下边界称为下包。整个集合的凸包由上包和下包构成。如图8-2所示。







2.算法求解步骤 构造上包的步骤:
步骤1:找到子集S1中的点Pmax,它是距离线段P0Pn-1最远的点。也就是说,点Pmax、点P0、Pn-1组成的三角形是子集S1中所有点和点P0、Pn-1组成的三角形中面积最大的。
如何找S1中的Pmax呢?
利用解析几何中的知识:给定三个点P1(x1,y1),P2(x2,y2),P3(x3,y3),那么△P1P2P3的面积等于下列式子绝对值的二分之一。
x1x2x3
y1y2 x1y2 x3y1 x2y3 x3y2 x2y1 x1y3 (8-15) y3当且仅当点P3位于12的左侧时,式(8-15)的符号为正。因此,利用该式子可以在有限时间内检测某个点是否位于两个点所确定直线的左侧,并且可以求得这个点到这条直线的距离。
步骤2:连接0max,maxn 1。找出S1中位于直线0max左边的点,这些点构成集合S11;找出S1中位于直线maxn 1左边的点,这些点构成集合S12;△P0PmaxPn-1内部的点不予考虑。如图8-3所示。

第8章 数论算法及计算几何算法_数学_自然科学_专业资料。数论算法及计算几何算法,凸包问题及最接近点对问题的分治法第八章 数论算法及计算几何算法 教学目标 ? ...
第8章 数论算法及计算几何算法_数学_自然科学_专业资料。第八章 数论算法及计算几何算法 教学目标 ? 理解求最大公约数的算法 ? 掌握欧几里德公式的推广 ? ...
第八章 数论算法及计算几何算法 8.5 凸包问题 1、问题提出 ? 给定一个点集S={P0,P1,…,Pn-1},它的凸包是一 个最小的凸多边形P,且满足S中的每个点...
数论和计算几何_数学_自然科学_专业资料。pascal数论和计算几何数论和计算几何 ... 第八章 数论算法及计算几... 28页 免费 数论计算 引言 57页 免费 计算与...
第八章 数论算法及计算几... 28页 免费 奥数几何,数论,行程专题 8页 7...快速幂是用来快速计算a^n mod p的一种方 法。 如果n是偶数则a^n=a^(n/...
离散数学--11.1-2初等数论 24页 免费 数论-第八章 14页 1财富值 108第八章数论及其猜想的意... 41页 1财富值 第八章 数论算法及计算几何... 暂无...
第八章 数论算法及计算几何... 第九章 NP完全理论1/2 相关文档推荐 第2章 贪心法 56页 5财富值 第2章 贪心法 暂无评价 42页 1财富值 第2章 贪心法 ...
[编辑本段] 算法分类 算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论 的算法、动态规划以及数值分析、加密算法、排序算法、检索...
三角形几何运算 7页 免费 第8章 数论算法及计算几何... 暂无评价 32页 免费 CAGD第八章曲线的几何处理... 5页 5财富值 计算几何 67页 免费喜欢此文档的...
224 第八章 数论算法及计算几何算法 ... 226 8.1 最大公约数......
热门文档