半平面交的算法及其應(yīng)用

文檔來源:從網(wǎng)收集整理.word版本可.迎下支持.半平面交的算法及其用基本概念半平面：平面上的直及其一的部分，在直角坐系中可由不等式ax+by+c>=0確定。在一個(gè)有界區(qū)域里（在際算不妨一個(gè)足大的界），半平面或半平面的交是一個(gè)凸多形區(qū)域。n個(gè)半平面的交H∩H2∩?∩Hn是一個(gè)至多n條的凸多形。算法半平面交的機(jī)算法procedureintersectionofhalf-planesn個(gè)半平面1,H2?Hnaix+biy+ci>=0，i=1,2,3?nH∩H2∩?∩Hn初始化區(qū)域A整個(gè)平面依次用直ix+biy+ci=0，i=1,2,?n切割A(yù)，保留使不等式aix+biy+ci>=0成立的部分A本算法的度O(n*n)，并具有機(jī)的點(diǎn)。半平面交的分治算法假可以在O(m+n)的m個(gè)半平面的交和n個(gè)半平面的交合并，可以有一種O(n*log(n))的分治算法求半平面的交。Procedureintersectionofhalf-plane(D&C)n個(gè)半平面1,H2?Hnaix+biy+ci>=0，i=1,2,3?n

H∩H2∩?∩Hn將H1?Hn分成兩個(gè)大小近似相等的集合在每個(gè)子算半平面的交合并兩個(gè)凸多形區(qū)域形成H∩H∩?∩Hn所以就是怎在O(m+n)的形的交。如左所示，在O(m+n)的形沿平行于y方向切割成至多O(m+n)個(gè)梯形區(qū)域，每?jī)蓚€(gè)梯形區(qū)域的交可以在O(1)確定凸多形采用了一種特殊的方法?？梢钥闯鐾苟嘈紊戏胶拖路降臉?gòu)成了一個(gè)x坐兩個(gè)序列中的點(diǎn)分作一個(gè)表存得到確定凸多形區(qū)域的上界和下界。1文檔來源:從網(wǎng)收集整理.word版本可.迎下支持.算法：procedureintersectionofconvexpolygon形區(qū)域、BC=A∩B將兩個(gè)凸多形的點(diǎn)x坐分，得到序列xi,i=1?p初始化區(qū)域C空。理{x}依次理區(qū)域(xi,xi+1],i=1?p-1。算兩個(gè)多形在此區(qū)域里截得的梯形（可能退化ABCD和’’’求交點(diǎn)AB∩’AB∩’CD∩’將存在的點(diǎn)按x坐排序，除重復(fù)，添加到C的上界中。用似的方法求C的下界算此區(qū)域的右EF=BC∩’將、F分加入C的上界和下界。出C步：由于A、B的上下界x坐分有序，可采用并排序。復(fù)度O(m+n)步：由于是按照x增的序描些區(qū)域，每條界上的指在整個(gè)程中始向右移形的每個(gè)點(diǎn)至多描一次。復(fù)度O(m+n)。因此整個(gè)算法的度O(m+n)。問1：HotterandColder(Waterloolocalcontest)述：A和B在10*10的棋上行一個(gè)游。A確定一個(gè)點(diǎn)P，B每回合移一次。每次A都會(huì)告，他當(dāng)前所的位置是離P更近了(Hot)是更了(Cold)距離不的情況。）A每次回答后，確定P點(diǎn)可能存在的區(qū)域的面。分析：假B從C（x,y）移到了2,y)，A回答Hot。對(duì)P(x,y)所

足|CP|>|DP|，即：(2*x-2*x)*x+(2*y-2*y)*y+x1*x+y1*y12*x-y2*y>0。Cold初始可能的區(qū)域是[0,10]*[0,10]。每回合后都用相的不等式區(qū)域求交。并出交的面。問2：Milk(OOPC1)述：SRbGa有一凸n形面包，和一盆面足大但深度為h的牛奶。他想蘸k次（每次都保面包垂直于盆底），使得面包蘸上牛奶的部分面最大。分析：2文檔來源:從網(wǎng)收集整理.word版本可.迎下支持.由于本使用深度先搜索。蘸每條都k條E?k的方法，剩下的部分就應(yīng)于k個(gè)半平面和原多形的交。考察種蘸法，其中剩下的面最小的那種。問1是用幾個(gè)半平面次求交，并且每次都要出面。然采用機(jī)算法合適。問2如果用機(jī)算法，復(fù)度O(C(n,k)*n)，且便于在搜索的程中剪枝。如果用脫機(jī)的分治算法，復(fù)度O(C(n,k)*(n+k*log(k)))。問3：Video(CTSC98)述：已知一個(gè)多形P（不一定是凸的）P中是否存在點(diǎn)Q，在Q點(diǎn)能察到整個(gè)多形區(qū)域。分析：假多形的界點(diǎn)按逆出V01V?Vn，V=V。能ii+1的點(diǎn)Qi一定足QiVi*QiVi10,i0...n1而且能察到所有的點(diǎn)一定能形區(qū)域。如果用坐運(yùn)算，每個(gè)束條件都（也半平面）。本就化求n個(gè)半平面的交是否不空。問4：Triathlon(NEERC2000)述：n名手參加人三比按照手在三個(gè)段中所用的時(shí)排定名次。已知每名手在三個(gè)目中的速度Ui、Vi、i。問于手i，能否通適當(dāng)?shù)陌才湃齻€(gè)段的度（但每個(gè)段的度都不能來保他分析：假三個(gè)段的度分為、、，i次不等式，由于z>0，所以不妨將每個(gè)不等式兩都除以并令X=x/z，Y=y/z，就得到：本就化求n-1個(gè)不等式并判斷其面是否大于（即排除空集、點(diǎn)、段的情況）。問3和，最都化二元不等式解的存在性可以用分治算法有效地解決。問5：Runaway（CERC99）述：3文檔來源:從網(wǎng)收集整理.word版本可.迎下支持.在一個(gè)矩形R中有n個(gè)點(diǎn)P?Pn，找出一個(gè)點(diǎn)Q∈R使得min(|QPi|)最大。分析：將R分成n個(gè)區(qū)域，Q1?Q，Qi是離Pi點(diǎn)的距離比離其它點(diǎn)都小的點(diǎn)的集合：Qi可通在Pij的中垂Pi一的半平面的交求得。i一個(gè)凸多形。在Qi里，離Pi最的點(diǎn)只能出在Qi的點(diǎn)上。求其中最的點(diǎn)即可。求半平面的交采用分治算法，復(fù)度O(n*log(n))，對(duì)于Pi的多形最多有個(gè)點(diǎn)，因此求Qi中的最點(diǎn)復(fù)度O(n)。度O(n*n*log(n))。實(shí)上，由以上方法定的n個(gè)多形區(qū)域1?Qn就成了一個(gè)。Voronoi是算幾何中次于凸包的幾何象，有著非常廣泛的應(yīng)用。利用半平面的交求Vor