244 O(1)n 3
T(n)
2T(n/2) O(n)n 3
解此递归方程可得T(n)=O(nlogn)。
在一维情形下,更容易想到的解决方法是先排序,再线性扫描就可以了。但是这种方法不容易推广到二维情形。上述分治思想的解决方法很容易推广到二维的情形。
2.二维情形 (1)算法思想
选取一垂直线l:x=xm作为分割线。其中xm为S中各点x坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2,并设d=min{d1,d2},S中的最接近点对或者是d所对应的点对,或者是S1中的某个点p和S2中的某个点q组成的点对(p,q)。如何找出点对(p,q)呢?如果|p-q|小于d,则p点分布在P1带形区域内(左虚线和分割线l所夹的区域),q点分布在P2带形区域内(右虚线和分割线l所夹的区域)。如图8-5所示。













另外,对于P1中任意一点p,与它距离小于d的点分布在以p点为圆心,以d为半径的圆内。因此,与点p构成最接近点对的P2中的点一定落在一个d×2d的矩形R中。如图8-6所示。




m
在矩形R中,有多少个点可能与P1中的点p构成最接近点对呢?由d的意义可知,矩形R中任何两个S中的点的距离都大于等于d。由此可知,至少可以将d×2d的矩形R分割成如图8-7所示的六部分,其中任何一部分包含P2中的点最多有一个,如果包含P2中的两个点,则这两个点的距离最大为:(d/2) (2d/3) 5d/6<d。这与P2中任何两个S
2
2
图8-6 包含点q的d×2d矩形区R
第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 最大公约数......
热门文档