1、半平面交的算法及其应用半平面交的算法及其应用北京四中李澎煦基本概念半平面：半平面：平面上的直线及其一侧的部分。半平面可由不等式ax+by+c=0确定。在一个有界区域里半平面或半平面的交是一个凸多边形区域。n个半平面的交是一个至多n条边的凸多边形。半平面交的联机算法procedure intersection of half-planes输入：n个半平面H1,H2,Hn输出：H1H2Hn初始化区域A为整个平面依次用直线aix+biy+ci=0，i=1,2,n切割A，保留使不等式aix+biy+ci=0成立的部分输出 A复杂度O(n*n)，联机算法。半平面交的分治算法假设可以在O(m+n)的时间内
2、将m个半平面的交和n个半平面的交合并，则可以有一种O(n*log(n)的分治算法求半平面的交。Procedure intersection of half-plane(D&C)输入：n个半平面H1,H2,Hn输出：H1H2Hn将H1Hn分成两个大小近似相等的集合在每个子问题中递归地计算半平面的交合并两个凸多边形区域形成H1H2Hn问题的关键是怎样在O(m+n)的时间里求两个凸多边形的交。将两个凸多边形沿顶点切割成至多O(m+n)个平行于y轴的梯形区域每两个梯形区域的交可以在O(1)时间内解决 凸多边形上方和下方的顶点分别构成一个x坐标递增序列。将这两个序列中的顶点分别作为一个链表存储,得到确定
3、凸多边形区域的上界和下界。描述凸多边形的方法凸多边形交的算法1：procedure intersection of convex polygon输入：两个凸多边形区域A、B输出：C=AB1.将两个凸多边形的顶点x坐标分类，得到序列xi,i=1p2.初始化区域C为空。3.处理x14.依次处理区域(xi,xi+1,i=1p-1。5.输出C凸多边形交的算法2：计算两个多边形在此区域里截得的梯形（可能退化）计算两个多边形在此区域里截得的梯形（可能退化）:ABCD和和ABCD。4.2 求交点求交点ABAB、ABCD、CDAB，将存在的，将存在的点按点按x坐标排序，删除重复，添加到坐标排序，删除重复，添加
4、到C的上界中。的上界中。4.3 用类似的方法求用类似的方法求C的下界的下界4.4 计算此区域的右侧边界计算此区域的右侧边界(线段的交）：线段的交）：EF=BCBC。将。将E、F分别加入到分别加入到C的上界和下界中。的上界和下界中。4.依次处理区域(xi,xi+1,i=1p-1。AB(E)C(F)DABCD算法的复杂度 步1：由于A、B的上下界x坐标分别有序，可采用归并排序。复杂度O(m+n)步4：由于是按照x递增的顺序扫描这些区域，每条边界上的指针在整个过程中始终向右移动。两个多边形的每个顶点至多扫描一次。复杂度为O(m+n)。整个算法的时间复杂度为O(m+n)。Hotter and Cold
5、er(Waterloo local contest)问题1A和B在10*10的棋盘上进行一个游戏。A确定一个点P，B每回合移动一次。每次A都会告诉B，他当前所处的位置是离P更近了(Hot)还是更远了(Cold)。（原题还要考虑距离不变的情况。）请在A每次回答后，确定P点可能存在的区域的面积。问题1分析：假设B从C（x1,y1）移动到了D(x2,y2)，A回答Hot。那么P(x,y)所处的位置就满足|CP|DP|，即：2(x2-x1)x+2(y2-y1)y+x12+y12-x22-y220 类似地，回答Cold对应于另一个不等式。初始时可能的区域是0,10*0,10。每回合后都用相应的不等式对应
6、的半平面与当前区域求交。并输出交的面积。Nice Milk (OOPC1)问题2SRbGa有一块凸n边形面包，和一盆面积足够大但深度仅为h的牛奶。他想仅蘸k次（每次都保证面包垂直于盆底），使得面包蘸上牛奶的部分面积最大。问题2分析：由于本题规模不大，考虑使用深度优先搜索。蘸每条边都对应剩下的一个半平面，某种蘸k条边E1Ek的方法，剩下的部分就对应于这k个半平面和原多边形的交。考察C(n,k)种蘸法，选其中剩下面积最小的那种。小结问题问题1 1是用几个半平面顺次求交，并且每是用几个半平面顺次求交，并且每次都要输出面积。显然采用联机算法合次都要输出面积。显然采用联机算法合适。适。问 题问 题 2
7、2 如 果 用 联 机 算 法，复 杂 度 为如 果 用 联 机 算 法，复 杂 度 为OC(n,k)OC(n,k)*n n，且便于在搜索的过程中剪，且便于在搜索的过程中剪枝。如果用脱机的分治算法，复杂度为枝。如果用脱机的分治算法，复杂度为OC(n,k)OC(n,k)*(n+k(n+k*log(k)log(k)。Video (CTSC98)问题问题3 3：已知一个多边形P（不一定是凸的）问在P中是否存在点Q，在Q点能观察到整个多边形区域。问题3分析：若多边形的顶点按逆时针顺序给出V0V1V2Vn，V0=Vn。则能够观察到边ViVi+1的点Qi一定满足 能观察到所有边的点一定能够观察到整个多边形
8、区域。如果用坐标进行叉积运算，则每个约束条件都对应一个二元一次不等式（也对应于一个半平面）。本题就转化为求这n个半平面的交是否不为空。1.0,0*niVQVQjiiiTriathlon (NEERC2000)问题问题4 4：n名选手参加铁人三项赛，比赛按照选手在三个赛段中所用的总时间排定名次。已知每名选手在三个项目中的速度Ui、Vi、Wi。问对于选手i，能否通过适当的安排三个赛段的长度（但每个赛段的长度都不能为0），来保证他获胜。问题4分析：假设三个赛段的长度分别为x、y、z，则选手i获胜的充要条件就是：这是一个三元齐次不等式组，由于z0，所以不妨将每个不等式两侧都除以z,并令X=x/z，Y=
9、y/z，就得到 本题就转化为求这n-1个不等式对应的半平面的交，并判断其面积是否大于0（即排除空集、点、线的情况）。jjjiiiwzvyuxwzvyux0111111ijijijwwYvvXuu小结问题问题3 3和问题和问题4 4，最终都转化为二元不等，最终都转化为二元不等式组解的存在性问题。可以用半平面交式组解的存在性问题。可以用半平面交的分治算法有效地解决。的分治算法有效地解决。但两个问题又略有不同，一个是但两个问题又略有不同，一个是=0=0、一、一个是个是=0=0。也就是说对多边形的边界处理。也就是说对多边形的边界处理不同。不同。=0=0的不等式要考虑退化为点、线的不等式要考虑退化为点、
10、线的情况，稍微复杂一点。的情况，稍微复杂一点。Run away（CERC99）在一个矩形R中有n个点P1Pn，请找出一个点QR使 min(|QPi|)最大。问题问题5 5：问题5分析1：将R分成n个区域，Q1Qn，Qi是R里离Pi点的距离比离其它点都小的点的集合：Qi可通过在PiPj的中垂线Pi一侧的半平面的交求得。Qi为一个凸多边形。在Qi里，离Pi最远的点只能出现在Qi的顶点上。求其中最远的点即可。RjiQPQPQQjii,问题5分析2：半平面的交采用分治算法，每个点的复杂度为O(n*log(n)。对应于Pi的多边形最多有O(n)个顶点，因此求Qi中的最远点复杂度为O(n)。总的复杂度为O
11、(n*n*log(n)。Voronoi图 实际上，由以上方法定义的n个多边形区域Q1Qn就组成了一个VoronoiVoronoi图图。Voronoi图是计算几何中仅次于凸包的几何对象，有着非常广泛的应用。利用半平面的交求Voronoi图的算法不是最优的。分 治 法、平 面 扫 描 法 等 许 多 算 法 都 能 达 到O(n*log(n)的复杂度，这才是最优的。但这些算法都过于复杂，不属于本文讨论的范围。半平面交的算法及其应用基本概念算法半平面交的联机算法半平面交的分治算法应用问题1：Hotter and ColderHotter and Colder问题2：MilkMilk小结问题3：VideoVideo问题4：TriathlonTriathlon小结问题5：Run awayRun awayVoronoiVoronoi图
