第8章-數(shù)論算法及計算幾何算法 (1)

1、第八章 數(shù)論算法及計算幾何算法,8.5 凸包問題,1、問題提出給定一個點集S＝{P0,P1,…,Pn-1}，它的凸包是一個最小的凸多邊形P，且滿足S中的每個點或者在P的邊界上或者在P的內(nèi)部。 如果點集S是兩個點的集合，顯然它的凸包是連接這兩個點的線段；如果S是由三個不共線的點組成的集合，那么凸包是以這三個點為頂點的三角形；如果三點共線，則凸包是以距離最遠(yuǎn)的兩個點為端點的線段。對于更大的集合，在直觀上，可以把S中的每個點看作

2、訂在地上的木樁，那么凸包就是將所有木樁圍起來的一個拉緊的橡皮繩的形狀，如圖8-1所示。,,解決方法： 1、窮舉搜索法 2、分治法,1、算法思想 ： 根據(jù)凸多邊形的定義，對于一個由n個點組成的集合S中的任意兩個點Pi和Pj，當(dāng)且僅當(dāng)該集合中的其它點要么位于穿過Pi和Pj直線的同側(cè)，要么位于線段PiPj上。則線段PiPj是該集合凸多邊形邊界的一部分。對每一個點都做一遍檢驗之后，滿足條件的線段就構(gòu)成了該凸包的邊界。,8

3、.5.1凸包問題的窮舉搜索法,2、算法求解步驟 ：步驟1：對于集合中的任意兩點Pi和Pj ，定義穿過兩點Pi和Pj的直線方程 。 (x-xi) / (xj-xi) =(y-yi) / (yj-yi)步驟2：將點集S中的其余點代入直線方程，然后檢查是否位于線段同側(cè)，如果不是，說明線段PiPj不是點集S的凸多邊形的邊界。 否則，PiPj是凸多邊形的邊界。步驟3：對點集中的每個點，重復(fù)上述步驟

4、1和步驟2，直到找出全部多邊形的邊界。,3、算法程序語言描述 詳見課本4、算法分析 點集中的點構(gòu)成的線段數(shù)目最多為n(n-1)/2，對每一條線段，最壞情況要檢查點集中其余n-2個點屬于哪個半平面， 故算法的時間復(fù)雜性為O(n3),8.5.2凸包問題的分治法1、算法思想 將點集S中的點按照x坐標(biāo)升序排序，x坐標(biāo)相同的按照y坐標(biāo)升序排序，排好序的序列存放在點結(jié)構(gòu)數(shù)組P中。 那么最左邊的點P

5、0、最右邊的點Pn-1肯定是凸包上的點。 線段P0Pn-1將集合S中的點分成兩個集合S1和S2。,子集S1的凸包由線段P0Pn-1作為下邊界、多節(jié)鏈條作為上邊界組成。這條上邊界稱為上包。子集S2的凸包由線段P0Pn-1作為上邊界、多節(jié)鏈條作為下邊界組成。這條下邊界稱為下包。整個集合的凸包由上包和下包構(gòu)成。如圖8-2所示。,,2、算法求解步驟 構(gòu)造上包步驟：找到子集S1中的點Pmax，它是距離線段P0Pn-1最遠(yuǎn)的點 連

6、接 ，找出S1中位于直線 左邊的點，這些點構(gòu)成集合S11；找出S1中位于直線 左邊的點，這些點構(gòu)成集合S12；△P0PmaxPn-1內(nèi)部的點不予考慮。遞歸構(gòu)造S11和S12的上包，然后簡單地將它們連接起來，得到S1的上包。 構(gòu)造下包步驟：找到子集S2中的點Pmin，它是距離線段P0Pn-1最遠(yuǎn)的點 連接

7、 ，找出S2中位于直線 右邊的點，這些點構(gòu)成集合S21；找出S2中位于直線 右邊的點，這些點構(gòu)成集合S22；△P0PminPn-1內(nèi)部的點不予考慮遞歸構(gòu)造S21和S22的下包，然后簡單地將它們連接起來，得到S2的下包 。,,,3、 算法程序語言描述 詳見課本,8.6最接近點對問題,1、問題提出最接近點對問題要求給定平面上n個點組成的集合S，找出其中n個點組成的點對中距離最近的一對點

8、。該問題具有很大的實際應(yīng)用價值，例如，一個控制空中或者海上交通的系統(tǒng)就需要了解2個最近的交通工具，以預(yù)測可能產(chǎn)生的相撞事故。2、解決問題方法 窮舉搜索、分治法（略）,,8.6.1最接近點對問題的窮舉搜索法1、算法思想 分別計算點集中每一對點的距離Dij，從中找出值最小的那對點。 為了避免點對的重復(fù)計算，算法只考慮i<j的情況.2、算法描述Double shortdis( ){doubl

9、e 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]; }},3、算法分析從算法描

10、述可知循環(huán)體內(nèi)的時間是常數(shù)時間，循環(huán)次數(shù) ， 因此算法的時間復(fù)雜性為O(n2) 。,,8.6.2最接近點對問題的分治法1、算法思想 將所給平面上的n個點的集合S分成規(guī)模大致相等的兩個子集S1和S2。遞歸求解S1和S2中的最接近點對； 集合S中的最接近點對： 或者是子問題S1的解； 或者是子問題S2的解， 或者是一個點在S1中，一個點在S2中的情況組成的最接近點對。,一維情形下

11、最小點對：算法描述：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)。,,二維情形算法描述：Step1：選取

12、一垂直線l：x=xm作為分割線。其中xm為S中各點x坐標(biāo)的中位數(shù)。由此將S分割為S1和S2Step2：遞歸求S1中最接近點對，其距離為d1Step3：遞歸求S2中最接近點對，其距離為d2Step4：令d=min(d1,d2)Step5：找出S1中的某個點p和S2中的某個點q組成的點對(p,q) （難點）Step6：比較|p-q|,d1,d2確定哪個是最接近點對思考：如何找出點對(p,q) ？如果|p-q|小于d，則p點分布

13、在P1帶形區(qū)域內(nèi)(左虛線和分割線l所夾的區(qū)域)，q點分布在P2帶形區(qū)域內(nèi)(右虛線和分割線l所夾的區(qū)域)。如圖8-5所示,對于P1中任意一點p，與它距離小于d的點分布在以p點為圓心，以d為半徑的圓內(nèi)。因此，與點p構(gòu)成最接近點對的P2中的點一定落在一個d×2d的矩形R中。如圖8-6所示。,,,由d的意義可知，矩形R中任何兩個S中的點的距離都大于等于d。由此可知，至少可以將d×2d的矩形R分割成如圖8-7所示的六部分，其中