当前位置：文档之家 › 算法合集之《半平面交的算法及其应用》

算法合集之《半平面交的算法及其应用》

  • 格式：ppt
  • 大小：231.50 KB
  • 文档页数：24

下载文档原格式

  / 24

合集下载

半平面交的算法及其应用

半平面交的算法及其应用
(CTSC98) 已知一个多边形P（不一定是凸的）问在P 中是否存在点Q，在Q点能观察到整个多边形 区域。
问题3分析：
• 若多边形的顶点按逆时针顺序给出V0V1V2…Vn ， V0=Vn。则能够观察到边ViVi+1的点Qi一定满足
Q iV i * Q iV j 0 , i 0 ... n 1
小结
•问题1是用几个半平面顺次求交，并且每 次都要输出面积。显然采用联机算法合 适。 •问 题 2 如 果 用 联 机 算 法 ， 复 杂 度 为 O[C(n,k)*n] ，且便于在搜索的过程中剪 枝。如果用脱机的分治算法，复杂度为 O[C(n,k)*(n+k*log(k))]。
问题3：
Video
算法的复杂度
• 步1：由于A、B的上下界x坐标分别有序， 可采用归并排序。复杂度O(m+n) • 步4：由于是按照x递增的顺序扫描这些区 域，每条边界上的指针在整个过程中始终 向右移动。两个多边形的每个顶点至多扫 描一次。复杂度为O(m+n)。 • 整个算法的时间复杂度为O(m+n)。
问题1
Hotter and Colder
凸多边形交的算法2：
4.依次处理区域(xi,xi+1],i=1…p-1。
A A’ D’ D
B’ B(E)
C(F)
C’
4.1 计算两个多边形在此区域里截得的梯形（可能退化） :ABCD和A’B’C’D’。 4.2 求交点AB∩A’B’、AB∩C’D’、CD∩A’B’，将存在的点 按x坐标排序，删除重复，添加到C的上界中。 4.3 用类似的方法求C的下界 4.4 计算此区域的右侧边界(线段的交）：EF=BC∩B’C’ 。将E、F分别加入到C的上界和下界中。

平面分割问题c++

平面分割问题c++

平面分割问题c++
平面分割问题是计算几何中的一个经典问题，它的基本思想是将平面上的点集分割成若干个不相交的区域。

在c++中，我们可以使用多种算法来解决这个问题，例如扫描线算法，半平面交算法等等。

这些算法的实现都需要对点进行排序，对线段进行比较，判断点是否在多边形内部等等操作。

具体来说，扫描线算法是利用扫描线不断水平扫描平面上的点，当遇到线段时，通过比较线段的端点坐标来确定线段与扫描线的交点，然后根据交点的位置关系来更新当前扫描线上的区域。

半平面交算法则是通过不断添加半平面来逐步构建出多边形的边界，最终得到分割后的区域。

总之，平面分割问题在计算几何中具有重要的应用价值，它的解决需要借助于一些基本的数据结构和算法，如点、线段、多边形的表示方法，排序、比较、判定等等。

对于c++程序员来说，熟练掌握这些技术是非常重要的。

- 1 -。

半动态矩形交查询算法

半动态矩形交查询算法

半动态矩形交查询算法
高静波;李新友
【期刊名称】《软件学报》
【年(卷),期】1997(008)008
【摘要】本文讨论了动态矩形交查询算法.文中介绍了两个半动态矩形查询的新算法，它们分别基于一维数据结构和二维数据结构.一维查询算法的查询时间复杂度是O（logM＋k′），更新时间复杂度是O（logMlogn），空间复杂度是O （nlogM）.二维查询算法的查询时间复杂度是O（log2M＋k），更新时间复杂度是O（log2Mlogn），空间复杂度是O（nlog2M）.本文分别实现了这两个算法，通过对它们的性能进行比较，发现一维查询算法是一种高效、实用的算法.【总页数】8页(P577-584)
【作者】高静波;李新友
【作者单位】清华大学计算机科学与技术系CAD中心;清华大学计算机科学与技术系CAD中心
【正文语种】中文
【中图分类】TP391.41
【相关文献】
1.基于矩形编码的抖动半调图像无损压缩算法 [J], 张萍;孔月萍;江永林
2.基于线段与线段求交的矩形窗口裁剪算法 [J], 刘中琦;秦敬超;聂如春
3.求解二维正交矩形布局问题的动态填空启发式算法 [J], 孙宝金;贺良华
4.基于动态参数差分进化算法的多约束稀布矩形面阵优化 [J], 姚敏立; 王旭健; 张峰干; 戴定成
5.基于动态择优定序的矩形件优化排板算法 [J], 鞠云鹏;常德功
因版权原因，仅展示原文概要，查看原文内容请购买。

算法合集之《半平面交的算法及其应用》

算法合集之《半平面交的算法及其应用》

半平面交的算法及其应用基本概念半平面：平面上的直线及其一侧的部分，在直角坐标系中可由不等式ax+by+c>=0确定。

在一个有界区域里（在实际计算时不妨设一个足够大的边界），半平面或半平面的交是一个凸多边形区域。

n个半平面的交H1∩H2∩…∩H n是一个至多n条边的凸多边形。

算法半平面交的联机算法procedure intersection of half-planes输入：n个半平面H1,H2,…H n对应的不等式组a i x+b i y+c i>=0，i=1,2,3…n输出：H1∩H2∩…∩H n初始化区域A为整个平面依次用直线a i x+b i y+c i=0，i=1,2,…n切割A，保留使不等式a i x+b i y+c i>=0成立的部分输出A本算法的时间复杂度为O(n*n)，并具有联机的优点。

半平面交的分治算法假设可以在O(m+n)的时间内将m个半平面的交和n个半平面的交合并，则可以有一种O(n*log(n))的分治算法求半平面的交。

Procedure intersection of half-plane (D&C)输入：n个半平面H1,H2,…H n对应的不等式组a i x+b i y+c i>=0，i=1,2,3…n输出：H1∩H2∩…∩H n将H1…H n分成两个大小近似相等的集合在每个子问题中递归地计算半平面的交合并两个凸多边形区域形成H1∩H2∩…∩H n所以问题的关键就是怎样在O(m+n)的时间里求两个凸多边形的交。

形沿平行于y轴方向切割成至多O(m+n)个梯形区域，每两个梯形区域的交可以在O(1)时间内解决。

为了便于操作，确定凸多边形采用了一种特殊的方法。

可以看出凸多边形上方和下方的顶点分别构成了一个x坐标递增序列。

将这两个序列中的顶点分别作为一个链表存储,得到确定凸多边形区域的上界和下界。

算法：procedure intersection of convex polygon输入：两个凸多边形区域A、B输出：C=A∩B1.将两个凸多边形的顶点x坐标分类，得到序列x i,i=1…p2.初始化区域C为空。

算法合集之《欧几里得算法的应用》

算法合集之《欧几里得算法的应用》

算法合集之《欧几里得算法的应用》欧几里得算法，又称为辗转相除法，是求两个正整数的最大公约数的一种简便有效的方法。

它的基本原理是通过一系列的除法运算，将两个数逐渐缩小为它们的公约数，最终得到最大公约数。

在实际应用中，欧几里得算法有着非常广泛的应用。

以下将介绍几个常见的应用场景。

首先，欧几里得算法可以用来简化分数。

假设我们有一个分数a/b，其中a和b都是正整数，并且a大于b。

我们可以使用欧几里得算法求出a和b的最大公约数gcd(a, b)，然后将a和b都除以gcd(a, b)。

这样可以得到一个简化的分数，它与原来的分数等价，但是分子和分母的数值都更小。

这在数学计算和编程中都非常有用，可以提高计算效率和准确性。

其次，欧几里得算法可以用来判断两个数是否互质。

如果两个数a和b的最大公约数是1，那么我们称它们为互质数。

互质数在数论和密码学等领域中有着重要的应用。

例如，在RSA密码算法中，互质数的选择是非常关键的一步，以提高密码的安全性。

此外，欧几里得算法还可以用来求解线性方程。

考虑一个一元线性方程ax + by = c，其中a、b、c都是已知的整数。

如果方程有整数解，那么x和y的取值是有限的。

欧几里得算法可以用来求解这个方程的一个特殊解，我们称之为整数解。

具体方法是通过一系列的除法运算，将方程转化为一个简化的形式。

然后我们可以利用整数解的性质，通过修正系数的方法，逐步缩小方程的规模，最终得到方程的所有整数解。

最后，欧几里得算法还可以用来求解模线性方程组。

模线性方程组是一组形如ax ≡ b (mod m)的方程，其中a、b、m都是已知的整数。

模线性方程组在密码学和通信中有着广泛的应用。

欧几里得算法可以用来求解这个方程组的一个特殊解，我们称之为模线性方程组的基础解集。

基础解集可以通过一系列的除法运算和模运算，将方程组转化为一个简化的形式。

然后我们可以利用基础解集的性质，通过修正参数的方法，逐步缩小方程组的规模，最终得到方程组的所有解。

半平面求交算法

半平面求交算法

•Step 1: Separate the h-planes into two sets. One has polar angles of (-½π, ½π], the other has those of (-π, -½π]∪(½π, π].•将半平面分成两部分，一部分极角范围(-½π, ½π]，另一部分范围(-π, -½π]∪(½π, π]•Step 2: Consider the set of h-planes in (-½π, ½π] (the other set should also go through step 3 and 4 similarly). Sort them by the polar angle. For the h-planes with the same polar angle, we can keep only one down (delete all others) according to the constant of these h-planes •考虑(-½π, ½π]的半平面(另一个集合类似地做Step3/4)，将他们极角排序。

对极角相同的半平面，根据常数项保留其中之一。

•Step 3.1: Starting from two h-planes with the least polar angle, compute their intersection.Push them two into a stack.•从排序后极角最小两个半平面开始，求出它们的交点并且将他们押入栈。

•Step 3.2: Each time, add one more h-plane by increasing order of polar angles, and calculate the intersection of it and the top h-plane in stack.•每次按照极角从小到大顺序增加一个半平面，算出它与栈顶半平面的交点。

HDU3761JungleOutpost（二分+半平面交）

c xlove的程序员之路艰辛的旅途，but never give upH DU 3761 Jungle Outpost（二分+半平面交）分类： ACM_计算几何 2012-08-28 11:10 117人阅读 评论(0) 收藏举报转载请注明出处，谢谢/acm_cxlove/article/details/7854526 by---cxlove题目：给出一个凸多边形，顶点为一些防御塔，保护范围是凸多形内部，不包括边界，在多边形内部选择一点，使得对方至少需要摧毁的塔防数量最多。

/showproblem.php?pid=3761首先感谢晴天哥哥的悉心指导。

首先需要明白的是一个问题，对于摧毁一定数量的塔防，怎样的方案是使得剩下的保护范围最小。

结论是摧毁连续多个顶点，这样是最优的，可以尝试证明一下。

对于5个顶点的多边形，删除两个顶点，可以尝试连续两个顶点，以及间隔一个顶点。

由于原多边形是凸边形，所以还是比较容易得到连续顶点最优，同理可得其它情况。

题目要求的是使对方尽可能多的摧毁至少需要摧毁的塔防，联系复杂度等等问题二分答案，然后判断是否存在一个区域，保证能受保护。

对于每一次二分，枚举删除连续的顶点，形成新的边界，通过半平面交判断是否存在可行区域。

注意：边界上的点是不受保护的，所以只需要判断多边形的核的面积即可。

当剩余的点在2个以及以下是，是肯定可行的。

避免处理麻烦。

再看一看题目的范围，5W个顶点，半平面交至少肯定是要用nlgn的算法，其实听了晴天哥哥的说明，才知道，这题二分+半平面交的nlgnlgn的算法都要卡掉，顿时吓尿了，难道有o(n)的半平面交算法多亏晴天哥哥的指导，其实zzy的半平面交算法是将所有向量按极角排序之后，维护了一个双端队列，排序部分达到nlgn的复杂度，其实后面只需要o(n)。

然后再看这题，原先给的凸多形是有序的，而之后我们的连线的极角也是循环有序的，线性扫描一遍，找到最小的极角，便可以依次得到有序的向量，O(n)的线性sort,晴天哥哥太神了。

算法合集之《欧几里得算法的应用》


5 总结
14
∗mailto:crazyb0y@
1
1 欧几里得算法
这一节主要是简要介绍一些关于欧几里得算法的基础，如果您对其足够了解，请直接跳过
1.1 最大公约数
最大公约数问题是最早被研究的算法问题之一了1，并且是信息学竞赛中能涉及到的很 多数论内容，比如模线性方程，模线性方程组的基础。欧几里得算法 (Euclidean algorithm2) ，即大部分选手所知的“辗转相除法”，其核心在于不断将两数规模变小，最后实 现对数时间3内把问题变换到能直接判定解的规模。
5: for i = 1 → n do
6: for j = i + 1 → n do
7:
while Aj,i ̸= 0 do
8:
t ⇐ Ai,i div Aj,i
9:
Ai ⇐ Ai − Aj × t
10:
swap Ai and Aj
11:
ans ⇐ −ans
12: end while
13: end for
(1)
x4 − 4x3 + 4x2 − 3x + 14
(2)
x3
+
2 x2
+
5 x
−
2
(3)
3 33
x2 + x + 2
(4)
0
(5)
即可得到1与2的最大公因式为4。 多项式的最大公因式代表了两个多项式方程的公共根。
2.2 模意义下的矩阵行列式
题目来源 经典问题，一个例题是SPOJ Find The Determinant III89
乍看似乎欧几里得算法毫无神奇之处，但是当你发现了其逐步缩小规模的本质之后， 这种思想往往在做某些题目（包括数学计算机. . . ）会给你带来耳目一心的感觉。

半平面交




问题5分析2：
• 半平面的交采用分治算法，每个点的复杂度为 O(n*log(n))。 • 对应于 Pi 的多边形最多有 O(n) 个顶点，因此求 Qi中的最远点复杂度为O(n)。 • 总的复杂度为O(n*n*log(n))。
Voronoi图
• 实际上，由以上方法定义的n个多边形区域Q1…Qn 就组成了一个Voronoi图。 • Voronoi图是计算几何中仅次于凸包的几何对象， 有着非常广泛的应用。 • 利用半平面的交求Voronoi图的算法不是最优的。 • 分治法、平面扫描法等许多算法都能达到 O(n*log(n)) 的复杂度，这才是最优的。但这些算 法都过于复杂，不属于本文讨论的范围。
问题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-y22>0
• 类似地，回答Cold对应于另一个不等式。 • 初始时可能的区域是[0,10]*[0,10]。每回合后都用相应 的不等式对应的半平面与当前区域求交。并输出交的面 积。
Hotter and Colder
(Waterloo local contest)
A和B在10*10的棋盘上进行一个游戏。 A确定一个点 P， B每回合移动一次。每次 A都会告诉 B，他当前所处的位置是离 P更 近了 (Hot) 还是更远了 (Cold) 。（原题还要 考虑距离不变的情况。） 请在 A每次回答后，确定 P 点可能存在 的区域的面积。
凸多边形交的算法1：
procedure intersection of convex polygon 输入：两个凸多边形区域A、B 输出：C=A∩B 1.将两个凸多边形的顶点x坐标分类，得到序 列xi,i=1…p 2.初始化区域C为空。 3.处理{x1} 4.依次处理区域(xi,xi+1],i=1…p-1。 5.输出C

最全“一半”模型结论，掌握这些面积计算不再难

最全“⼀半”模型结论，掌握这些⾯积计算不再难
⼀半模型是等积变换模型的延伸，但是学⽣往往遇到此类题⽬之后很难想到⽤等积变换的⽅
法，所以专门提炼出⼀半模型，帮助学⽣加深此部分知识点的理解，提⾼⾯积计算的应⽤能
⼒。

长⽅形“⼀半”模型
下图当中阴影均占长⽅形ABCD的⼀半，如果把长⽅形换作平⾏四边形，下⾯结论仍然成⽴，只
是在考察当中多以长⽅形形式出现，如果换作平⾏四边形也要理解。

进⼀步可得如下阴影占长⽅形ABCD⾯积的四分之⼀：
如果把P点移动到下图位置，也就是P点在长⽅形两条长所在直线的外部，那可得阴影⾯积差
（⼤减⼩）占长⽅形ABCD⾯积的⼀半。

三⾓形“⼀半”模型
解释⼀下第⼆⾏第⼀个图形，三⾓形的三条中线在三⾓形内部交于⼀点，该点称作重⼼，三条
中线把三⾓形分成6个⼩三⾓形，这6个⼩三⾓形的⾯积是相等的，因此任取3个三⾓形的⾯积和
占三⾓形ABC⾯积的⼀半。

四边形“⼀半”模型
这三个结论⽐较简单，不⽤过多解释，其中中间的四边形对边中点连线把四边形分成四块，这
四块刚好可以拼成⼀个平⾏四边形。

感兴趣的可以拼⼀下试试。

梯形“⼀半”模型
梯形是四边形，所以四边形具备的⾯积性质梯形也具备，不过梯形的⼀组底边平⾏，还具备以
下性质，其中最后⼀个图形表⽰在两腰中点连线上任意取⼀点，所得图中阴影三⾓形占梯形⾯
积的⼀半，该点只要在腰中点连线上，在梯形外部也成⽴。

特殊“⼀半”模型
下图当中的正⽅形和长⽅形的边是平⾏的。

如果不平⾏则不成⽴。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

• 本题就转化为求这n-1个不等式对应的半平面的交， 并判断其面积是否大于0（即排除空集、点、线的情 况）。
小结
•问题3和问题4，最终都转化为二元不等 式组解的存在性问题。可以用半平面交 的分治算法有效地解决。 •但两个问题又略有不同，一个是=0、一 个是>=0。也就是说对多边形的边界处理 不同。>=0的不等式要考虑退化为点、线 的情况，稍微复杂一点。
问题4分析：
• 假设三个赛段的长度分别为x 、y、z，则选手i获胜的 充要条件就是： x y z x y z ui vi wi u j v j w j • 这是一个三元齐次不等式组，由于z>0，所以不妨将 每个不等式两侧都除以z,并令X=x/z，Y=y/z，就得到
1 u 1u X 1v 1v Y 1 w 1 w 0 j i j i j i
凸多边形交的算法2：
4.依次处理区域(xi,xi+1],i=1…p-1。
A A ’ D ’ D
B ’ B(E)
C(F)
C’
4.1 计算两个多边形在此区域里截得的梯形（可能退化） :ABCD和A’B’C’D’。 4.2 求交点AB∩A’B’、AB∩C’D’、CD∩A’B’，将 存在的点按x坐标排序，删除重复，添加到C的上界中 。 4.3 用类似的方法求C的下界 4.4 计算此区域的右侧边界(线段的交）： EF=BC∩B’C’。将E、F分别加入到C的上界和下界 中。
问题的关键是怎样在O(m+n)的时间里求两 个凸多边形的交。
• 将两个凸多边形沿顶点 切割成至多O(m+n) 个 平 行于y轴的梯形区域 • 每两个梯形区域的交可 以在O(1)时间内解决
描述凸多边形的方法
• 凸多边形上方和下方的顶点分 别构成一个x坐标递增序列。 • 将这两个序列中的顶点分别作 为一个链表存储,得到确定凸多 边形区域的上界和下界。
小结
•问题1是用几个半平面顺次求交，并且每 次都要输出面积。显然采用联机算法合 适。 •问 题 2 如 果 用 联 机 算 法 ， 复 杂 度 为 O[C(n,k)*n]，且便于在搜索的过程中剪 枝。如果用脱机的分治算法，复杂度为 O[C(n,k)*(n+k*log(k))]。
问题3：
Video
• 能观察到所有边的点一定能够观察到整个多边形区 域。 • 如果用坐标进行叉积运算，则每个约束条件都对应 一个二元一次不等式（也对应于一个半平面）。本 题就转化为求这n个半平面的交是否不为空。
问题4：
Triathlon
(NEERC2000) n名选手参加铁人三项赛，比赛按照选手 在三个赛段中所用的总时间排定名次。已知每 名选手在三个项目中的速度Ui、Vi、Wi。 问对于选手i，能否通过适当的安排三个赛 段的长度（但每个赛段的长度都不能为0）， 来保证他获胜。
算法的复杂度
• 步1：由于A、B的上下界x坐标分别有序， 可采用归并排序。复杂度O(m+n) • 步4：由于是按照x递增的顺序扫描这些区 域，每条边界上的指针在整个过程中始终 向右移动。两个多边形的每个顶点至多扫 描一次。复杂度为O(m+n)。 • 整个算法的时间复杂度为O(m+n)。
问题1
Hotter and Colder
复杂度O(n*n)，联机算法。
半平面交的分治算法
假设可以在O(m+n)的时间内将m个半平面的交 和n个半平面的交合并，则可以有一种O(n*log(n))的 分治算法求半平面的交。
Procedure intersection of half-plane (D&C)
输入：n个半平面H1,H2,…Hn 输出：H1∩H2∩…∩Hn 将H1…Hn分成两个大小近似相等的集合 在每个子问题中递归地计算半平面的交 合并两个凸多边形区域形成H1∩H2∩…∩Hn
(CTSC98) 已知一个多边形P（不一定是凸的）问在P 中是否存在点Q，在Q点能观察到整个多边形 区域。
问题3分析：
• 若多边形的顶点按逆时针顺序给出V 0 V 1 V 2 …V n ， V0=Vn。则能够观察到边ViVi+1的点Qi一定满足
QiVi * QiV j 0, i 0...n 1
问题5：
Run away
（CERC99）
在一个矩形R中有n个点P1…Pn，请找出 一个点Q∈R使 min(|QPi|)最大。
问题5分析1：
• 将R分成n个区域，Q1…Qn，Qi是R里离Pi点的距离比离 其它点都小的点的集合：
Qi Q QPi QPj , i j R
• Qi可通过在PiPj的中垂线Pi一侧的半平面的交求得。Qi 为一个凸多边形。 • 在Q i 里，离P i 最远的点只能出现在Q i 的顶点上。求其 中最远的点即可。
凸多边形交的算法1：
procedure intersection of convex polygon 输入：两个凸多边形区域A、B 输出：C=A∩B 1.将两个凸多边形的顶点x坐标分类，得到序 列xi,i=1…p 2.初始化区域C为空。 3.处理{x1} 4.依次处理区域(xi,xi+1],i=1…p-1。 5.输出C
(Waterloo local contest)
A和B在10*10的棋盘上进行一个游戏。 A确定一个点P，B每回合移动一次。每次 A都会告诉B，他当前所处的位置是离P更 近了(Hot)还是更远了(Cold)。（原题还要 考虑距离不变的情况。） 请在A每次回答后，确定P点可能存在 的区域的面积。
问题1分析：
半平面交的算法及其应用
北京四中 李澎煦
基本概念
• 半平面：平面上的直线及其一侧的部分。 • 半平面可由不等式ax+by+c>=0确定。 • 在一个有界区域里半平面或半平面的交是 一个凸多边形区域。 • n个半平面的交是一个至多n条边的凸多边 形。
半平面交的联机算法
procedure intersection of half-planes 输入：n个半平面H1,H2,…Hn 输出：H1∩H2∩…∩Hn 初始化区域A为整个平面 依次用直线aix+biy+ci=0，i=1,2,…n切割A， 保留使不等式aix+biy+ci>=0成立的部分 输出 A
• 假设B从C（ x1 ,y 1）移动到了D(x 2,y2 )，A回答Hot。那么 P(x,y)所处的位置就满足 |CP|>|DP|，即：
2(x2-x1)x+2(y2-y1)y+x12+y12-x22-y22>0
• 类似地，回答Cold对应于另一个不等式。 • 初始时可能的区域是[0,10]*[0,10]。每回合后都用相应 的不等式对应的半平面与当前区域求交。并输出交的面 积。


问题5分析2：
• 半平面的交采用分治算法，每个点的复杂度为 O(n*log(n))。 • 对应于P i 的多边形最多有O(n)个顶点，因此求 Qi中的最远点复杂度为O(n)。 • 总的复杂度为O(n*n*log(n))。
Voronoi图
• 实际上，由以上方法定义的n个多边形区域Q1…Qn 就组成了一个Voronoi图。 • Voronoi图是计算几何中仅次于凸包的几何对象， 有着非常广泛的应用。 • 利用半平面的交求Voronoi图的算法不是最优的。 • 分治法、平面扫描法等许多算法都能达到 O(n*log(n))的复杂度，这才是最优的。但这些算 法都过于复杂，不属于本文讨论的范围。
问题2
Nice Milk
(OOPC1)
SRbGa有一块凸n边形面包，和一盆面 积 蘸上牛奶的部分面积最大。
问题2分析：
• 由于本题规模不大，考虑使用深度优先搜索。 • 蘸每条边都对应剩下的一个半平面，某种蘸k条边 E1…Ek的方法，剩下的部分就对应于这k个半平面 和原多边形的交。 • 考察C(n,k)种蘸法，选其中剩下面积最小的那种。
半平面交的算法及其应用
•基本概念 •算法 •半平面交的联机算法 •半平面交的分治算法 •应用 •问题1：Hotter and Colder •问题2：Milk •小结 •问题3：Video •问题4：Triathlon •小结 •问题5：Run away •Voronoi图