算法合集之《半平面交的算法及其應(yīng)用》

1、半平面交的算法及其應(yīng)用基本概念 半平面：平面上的直線及其一側(cè)的部分，在直角坐標(biāo)系中可由不等式ax+by+c>=0確定。在一個(gè)有界區(qū)域里（在實(shí)際計(jì)算時(shí)不妨設(shè)一個(gè)足夠大的邊界），半平面或半平面的交是一個(gè)凸多邊形區(qū)域。n個(gè)半平面的交H1H2Hn是一個(gè)至多n條邊的凸多邊形。算法半平面交的聯(lián)機(jī)算法procedure intersection of half-planes輸入：n個(gè)半平面H1,H2,Hn對(duì)應(yīng)的不等式組aix+biy+ci>=0，i=1,2,3n輸出：H1H2Hn初始化區(qū)域A為整個(gè)平面依次用直線aix+biy+ci=0，i=1,2,n切割A(yù)，保留使不等式aix+biy+ci>

2、;=0成立的部分輸出A本算法的時(shí)間復(fù)雜度為O(n*n)，并具有聯(lián)機(jī)的優(yōu)點(diǎn)。半平面交的分治算法假設(shè)可以在O(m+n)的時(shí)間內(nèi)將m個(gè)半平面的交和n個(gè)半平面的交合并，則可以有一種O(n*log(n)的分治算法求半平面的交。Procedure intersection of half-plane (D&C)輸入：n個(gè)半平面H1,H2,Hn對(duì)應(yīng)的不等式組aix+biy+ci>=0，i=1,2,3n輸出：H1H2Hn將H1Hn分成兩個(gè)大小近似相等的集合在每個(gè)子問(wèn)題中遞歸地計(jì)算半平面的交合并兩個(gè)凸多邊形區(qū)域形成H1H2Hn所以問(wèn)題的關(guān)鍵就是怎樣在O(m+n)的時(shí)間里求兩個(gè)凸多邊形的交。如左圖所

3、示，在O(m+n)的時(shí)間內(nèi)將兩個(gè)凸多邊形沿平行于y軸方向切割成至多O(m+n)個(gè)梯形區(qū)域，每?jī)蓚€(gè)梯形區(qū)域的交可以在O(1)時(shí)間內(nèi)解決。為了便于操作，確定凸多邊形采用了一種特殊的方法?？梢钥闯鐾苟噙呅紊戏胶拖路降捻旤c(diǎn)分別構(gòu)成了一個(gè)x坐標(biāo)遞增序列。將這兩個(gè)序列中的頂點(diǎn)分別作為一個(gè)鏈表存儲(chǔ),得到確定凸多邊形區(qū)域的上界和下界。算法：procedure intersection of convex polygon輸入：兩個(gè)凸多邊形區(qū)域A、B輸出：C=AB1. 將兩個(gè)凸多邊形的頂點(diǎn)x坐標(biāo)分類，得到序列xi,i=1p2. 初始化區(qū)域C為空。3. 處理x14. 依次處理區(qū)域(xi,xi+1,i=1p-1。4.

4、1計(jì)算兩個(gè)多邊形在此區(qū)域里截得的梯形（可能退化），設(shè)為ABCD和 ABCD。4.2求交點(diǎn)ABAB、ABCD、CDAB，將存在的點(diǎn)按x坐標(biāo)排序，刪除重復(fù)，添加到C的上界中。用類似的方法求C的下界4.3計(jì)算此區(qū)域的右側(cè)邊界：EF=BCBC。將E、F分別加入C的上界和下界。5.輸出C步1：由于A、B的上下界x坐標(biāo)分別有序，可采用歸并排序。復(fù)雜度O(m+n)步4：由于是按照x遞增的順序掃描這些區(qū)域，每條邊界上的指針在整個(gè)過(guò)程中始終向右移動(dòng)。兩個(gè)多邊形的每個(gè)頂點(diǎn)至多掃描一次。復(fù)雜度為O(m+n)。因此整個(gè)算法的時(shí)間復(fù)雜度為O(m+n)。應(yīng)用問(wèn)題1：Hotter and Colder (Waterloo

5、local contest)題目簡(jiǎn)述：A和B在10*10的棋盤(pán)上進(jìn)行一個(gè)游戲。A確定一個(gè)點(diǎn)P，B每回合移動(dòng)一次。每次A都會(huì)告訴B，他當(dāng)前所處的位置是離P更近了(Hot)還是更遠(yuǎn)了(Cold)。（原題還要考慮距離不變的情況。）請(qǐng)?jiān)贏每次回答后，確定P點(diǎn)可能存在的區(qū)域的面積。分析：假設(shè)B從C（x1,y1）移動(dòng)到了D(x2,y2)，A回答Hot。則對(duì)應(yīng)這一回合，點(diǎn)P(x,y)所處的位置滿足 |CP|>|DP|，即：(2*x2-2*x1)*x+(2*y2-2*y1)*y+x1*x1+y1*y1-x2*x2-y2*y2>0。類似地，回答Cold對(duì)應(yīng)于另一個(gè)不等式。初始時(shí)可能的區(qū)域是0,10*

6、0,10。每回合后都用相應(yīng)的不等式對(duì)應(yīng)的半平面與當(dāng)前區(qū)域求交。并輸出交的面積。問(wèn)題2：Milk (OOPC1)題目簡(jiǎn)述：SRbGa有一塊凸n邊形面包，和一盆面積足夠大但深度僅為h的牛奶。他想僅蘸k次（每次都保證面包垂直于盆底），使得面包蘸上牛奶的部分面積最大。分析：由于本題規(guī)模不大，考慮使用深度優(yōu)先搜索。蘸每條邊都對(duì)應(yīng)剩下的一個(gè)半平面，某種蘸k條邊E1Ek的方法，剩下的部分就對(duì)應(yīng)于這k個(gè)半平面和原多邊形的交?？疾霤(n,k)種蘸法，選其中剩下的面積最小的那種。問(wèn)題1是用幾個(gè)半平面順次求交，并且每次都要輸出面積。顯然采用聯(lián)機(jī)算法合適。問(wèn)題2如果用聯(lián)機(jī)算法，復(fù)雜度為O(C(n,k)*n)，且便于在

7、搜索的過(guò)程中剪枝。如果用脫機(jī)的分治算法，復(fù)雜度為O(C(n,k)*(n+k*log(k)。問(wèn)題3：Video (CTSC98)題目簡(jiǎn)述：已知一個(gè)多邊形P（不一定是凸的）問(wèn)在P中是否存在點(diǎn)Q，在Q點(diǎn)能觀察到整個(gè)多邊形區(qū)域。分析：假設(shè)多邊形的邊界點(diǎn)按逆時(shí)針?lè)较蚪o出V0V1V2Vn，V0=Vn。則能夠觀察到邊ViVi+1的點(diǎn)Qi一定滿足而且能觀察到所有邊的點(diǎn)一定能夠觀察到整個(gè)多邊形區(qū)域。如果用坐標(biāo)進(jìn)行叉積運(yùn)算，則每個(gè)約束條件都對(duì)應(yīng)一個(gè)二元一次不等式（也對(duì)應(yīng)于一個(gè)半平面）。本題就轉(zhuǎn)化為求這n個(gè)半平面的交是否不為空。問(wèn)題4：Triathlon (NEERC2000)題目簡(jiǎn)述：n名選手參加鐵人三項(xiàng)賽，比賽

8、按照選手在三個(gè)賽段中所用的總時(shí)間排定名次。已知每名選手在三個(gè)項(xiàng)目中的速度Ui、Vi、Wi。問(wèn)對(duì)于選手i，能否通過(guò)適當(dāng)?shù)陌才湃齻€(gè)賽段的長(zhǎng)度（但每個(gè)賽段的長(zhǎng)度都不能為0），來(lái)保證他獲勝。分析：假設(shè)三個(gè)賽段的長(zhǎng)度分別為x、y、z，則選手i獲勝的充要條件就是：這是一個(gè)三元齊次不等式組，由于z>0，所以不妨將每個(gè)不等式兩側(cè)都除以z,并令X=x/z，Y=y/z，就得到：本題就轉(zhuǎn)化為求這n-1個(gè)不等式對(duì)應(yīng)的半平面的交，并判斷其面積是否大于0（即排除空集、點(diǎn)、線段的情況）。問(wèn)題3和問(wèn)題4，最終都轉(zhuǎn)化為二元不等式組解的存在性問(wèn)題?？梢杂梅种嗡惴ㄝ^有效地解決。問(wèn)題5：Run away（CERC99）題目簡(jiǎn)述

9、：在一個(gè)矩形R中有n個(gè)點(diǎn)P1Pn，請(qǐng)找出一個(gè)點(diǎn)QR使得 min(|QPi|)最大。分析：將R分成n個(gè)區(qū)域，Q1Qn，Qi是離Pi點(diǎn)的距離比離其它點(diǎn)都小的點(diǎn)的集合：Qi可通過(guò)在PiPj的中垂線Pi一側(cè)的半平面的交求得。Qi為一個(gè)凸多邊形。在Qi里，離Pi最遠(yuǎn)的點(diǎn)只能出現(xiàn)在Qi的頂點(diǎn)上。求其中最遠(yuǎn)的點(diǎn)即可。求半平面的交采用分治算法，復(fù)雜度為O(n*log(n)，對(duì)應(yīng)于Pi的多邊形最多有O(n)個(gè)頂點(diǎn)，因此求Qi中的最遠(yuǎn)點(diǎn)復(fù)雜度為O(n)?？偟膹?fù)雜度為O(n*n*log(n)。實(shí)際上，由以上方法定義的n個(gè)多邊形區(qū)域Q1Qn就組成了一個(gè)Voronoi圖。Voronoi圖是計(jì)算幾何中僅次于凸包的幾何對(duì)象，有著非常廣泛的應(yīng)用。利用半平面的交求Voronoi圖的方法并不是最優(yōu)的，分治法、平面掃