半平面交的算法及其应用

文档来源:从网收集整理.word版本可.迎下支持.半平面交的算法及其用基本概念半平面：平面上的直及其一的部分，在直角坐系中可由不等式ax+by+c>=0确定。在一个有界区域里（在际算不妨一个足大的界），半平面或半平面的交是一个凸多形区域。n个半平面的交H∩H2∩⋯∩Hn是一个至多n条的凸多形。算法半平面交的机算法procedureintersectionofhalf-planesn个半平面1,H2⋯Hnaix+biy+ci>=0，i=1,2,3⋯nH∩H2∩⋯∩Hn初始化区域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分成两个大小近似相等的集合在每个子算半平面的交合并两个凸多形区域形成H∩H∩⋯∩Hn所以就是怎在O(m+n)的形的交。如左所示，在O(m+n)的形沿平行于y方向切割成至多O(m+n)个梯形区域，每两个梯形区域的交可以在O(1)确定凸多形采用了一种特殊的方法。可以看出凸多形上方和下方的构成了一个x坐两个序列中的点分作一个表存得到确定凸多形区域的上界和下界。1文档来源:从网收集整理.word版本可.迎下支持.算法：procedureintersectionofconvexpolygon形区域、BC=A∩B将两个凸多形的点x坐分，得到序列xi,i=1⋯p初始化区域C空。理{x}依次理区域(xi,xi+1],i=1⋯p-1。算两个多形在此区域里截得的梯形（可能退化ABCD和’’’求交点AB∩’AB∩’CD∩’将存在的点按x坐排序，除重复，添加到C的上界中。用似的方法求C的下界算此区域的右EF=BC∩’将、F分加入C的上界和下界。出C步：由于A、B的上下界x坐分有序，可采用并排序。复度O(m+n)步：由于是按照x增的序描些区域，每条界上的指在整个程中始向右移形的每个点至多描一次。复度O(m+n)。因此整个算法的度O(m+n)。问1：HotterandColder(Waterloolocalcontest)述：A和B在10*10的棋上行一个游。A确定一个点P，B每回合移一次。每次A都会告，他当前所的位置是离P更近了(Hot)是更了(Cold)距离不的情况。）A每次回答后，确定P点可能存在的区域的面。分析：假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初始可能的区域是[0,10]*[0,10]。每回合后都用相的不等式区域求交。并出交的面。问2：Milk(OOPC1)述：SRbGa有一凸n形面包，和一盆面足大但深度为h的牛奶。他想蘸k次（每次都保面包垂直于盆底），使得面包蘸上牛奶的部分面最大。分析：2文档来源:从网收集整理.word版本可.迎下支持.由于本使用深度先搜索。蘸每条都k条E⋯k的方法，剩下的部分就应于k个半平面和原多形的交。考察种蘸法，其中剩下的面最小的那种。问1是用几个半平面次求交，并且每次都要出面。然采用机算法合适。问2如果用机算法，复度O(C(n,k)*n)，且便于在搜索的程中剪枝。如果用脱机的分治算法，复度O(C(n,k)*(n+k*log(k)))。问3：Video(CTSC98)述：已知一个多形P（不一定是凸的）P中是否存在点Q，在Q点能察到整个多形区域。分析：假多形的界点按逆出V01V⋯Vn，V=V。能ii+1的点Qi一定足QiVi*QiVi10,i0...n1而且能察到所有的点一定能形区域。如果用坐运算，每个束条件都（也半平面）。本就化求n个半平面的交是否不空。问4：Triathlon(NEERC2000)述：n名手参加人三比按照手在三个段中所用的时排定名次。已知每名手在三个目中的速度Ui、Vi、i。问于手i，能否通适当的安排三个段的度（但每个段的度都不能来保他分析：假三个段的度分为、、，i次不等式，由于z>0，所以不妨将每个不等式两都除以并令X=x/z，Y=y/z，就得到：本就化求n-1个不等式并判断其面是否大于（即排除空集、点、段的情况）。问3和，最都化二元不等式解的存在性可以用分治算法有效地解决。问5：Runaway（CERC99）述：3文档来源:从网收集整理.word版本可.迎下支持.在一个矩形R中有n个点P⋯Pn，找出一个点Q∈R使得min(|QPi|)最大。分析：将R分成n个区域，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个多形区域1⋯Qn就成了一个。Voronoi是算几何中次于凸包的几何象，有着非常广泛的应用。利用半平面的交求Vor