半平面交的算法及其應用

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

H∩H2∩?∩Hn將H1?Hn分成兩個大小近似相等的集合在每個子算半平面的交合并兩個凸多形區(qū)域形成H∩H∩?∩Hn所以就是怎在O(m+n)的形的交。如左所示，在O(m+n)的形沿平行于y方向切割成至多O(m+n)個梯形區(qū)域，每兩個梯形區(qū)域的交可以在O(1)確定凸多形采用了一種特殊的方法?？梢钥闯鐾苟嘈紊戏胶拖路降臉?gòu)成了一個x坐兩個序列中的點分作一個表存得到確定凸多形區(qū)域的上界和下界。1文檔來源:從網(wǎng)收集整理.word版本可.迎下支持.算法：procedureintersectionofconvexpolygon形區(qū)域、BC=A∩B將兩個凸多形的點x坐分，得到序列xi,i=1?p初始化區(qū)域C空。理{x}依次理區(qū)域(xi,xi+1],i=1?p-1。算兩個多形在此區(qū)域里截得的梯形（可能退化ABCD和’’’求交點AB∩’AB∩’CD∩’將存在的點按x坐排序，除重復，添加到C的上界中。用似的方法求C的下界算此區(qū)域的右EF=BC∩’將、F分加入C的上界和下界。出C步：由于A、B的上下界x坐分有序，可采用并排序。復度O(m+n)步：由于是按照x增的序描些區(qū)域，每條界上的指在整個程中始向右移形的每個點至多描一次。復度O(m+n)。因此整個算法的度O(m+n)。問1：HotterandColder(Waterloolocalcontest)述：A和B在10*10的棋上行一個游。A確定一個點P，B每回合移一次。每次A都會告，他當前所的位置是離P更近了(Hot)是更了(Cold)距離不的情況。）A每次回答后，確定P點可能存在的區(qū)域的面。分析：假B從C（x,y）移到了2,y)，A回答Hot。對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的方法，剩下的部分就應于k個半平面和原多形的交?？疾旆N蘸法，其中剩下的面最小的那種。問1是用幾個半平面次求交，并且每次都要出面。然采用機算法合適。問2如果用機算法，復度O(C(n,k)*n)，且便于在搜索的程中剪枝。如果用脫機的分治算法，復度O(C(n,k)*(n+k*log(k)))。問3：Video(CTSC98)述：已知一個多形P（不一定是凸的）P中是否存在點Q，在Q點能察到整個多形區(qū)域。分析：假多形的界點按逆出V01V?Vn，V=V。能ii+1的點Qi一定足QiVi*QiVi10,i0...n1而且能察到所有的點一定能形區(qū)域。如果用坐運算，每個束條件都（也半平面）。本就化求n個半平面的交是否不空。問4：Triathlon(NEERC2000)述：n名手參加人三比按照手在三個段中所用的時排定名次。已知每名手在三個目中的速度Ui、Vi、i。問于手i，能否通適當?shù)陌才湃齻€段的度（但每個段的度都不能來保他分析：假三個段的度分為、、，i次不等式，由于z>0，所以不妨將每個不等式兩都除以并令X=x/z，Y=y/z，就得到：本就化求n-1個不等式并判斷其面是否大于（即排除空集、點、段的情況）。問3和，最都化二元不等式解的存在性可以用分治算法有效地解決。問5：Runaway（CERC99）述：3文檔來源:從網(wǎng)收集整理.word版本可.迎下支持.在一個矩形R中有n個點P?Pn，找出一個點Q∈R使得min(|QPi|)最大。分析：將R分成n個區(qū)域，Q1?Q，Qi是離Pi點的距離比離其它點都小的點的集合：Qi可通在Pij的中垂Pi一的半平面的交求得。i一個凸多形。在Qi里，離Pi最的點只能出在Qi的點上。求其中最的點即可。求半平面的交采用分治算法，復度O(n*log(n))，對于Pi的多形最多有個點，因此求Qi中的最點復度O(n)。度O(n*n*log(n))。實上，由以上方法定的n個多形區(qū)域1?Qn就成了一個。Voronoi是算幾何中次于凸包的幾何象，有著非常廣泛的應用。利用半平面的交求Vor