算法合集之《半平面交的新算法及其实用价值》课件.ppt

1、February 4,2023Zeyuan Zhu1All great ideas are controversial,or have been at one time.伟大的理论都是有争议的，或者至少伟大的理论都是有争议的，或者至少曾经是有争议的。曾经是有争议的。Gilbert Seldes(1893-1970)U.S.theater,film,and radio critic.理论的争议February 4,2023Zeyuan Zhu2A wise man will make more opportunities than he finds.聪明人总是制造更多的机会，而不是聪明人总是制造

2、更多的机会，而不是去等待寻找。去等待寻找。Francis Bacon(1561-1626)English philosopher,statesman,and lawyer.制造机会February 4,2023Zeyuan Zhu3After the leaves have fallen,we return to a plain sense of things.It is as if we had come to an end of the imagination.叶落时分，我们回到一切的本来面目，叶落时分，我们回到一切的本来面目，这样就与创造与幻想的终点不远了。这样就与创造与幻想的终点不远了

3、。Wallace Stevens(1879-1955)U.S.poet忘记过去，揭开本来面目February 4,2023Zeyuan Zhu4Hello,Ladies and Gentlemen.女士们先生们大家好女士们先生们大家好Bonjour,Mesdames et Messieurs.Witajcie,Panie i Panowie.Hallo,Damen und Herren.Buna ziua,Doamenelor si Domnilor.Ciao,signore e signori.Zeyuan Zhu,Grade 12,Nanjing Foreign Language Scho

4、ol,Jiangsu,China.朱泽园朱泽园,高三高三,南京市外国语学校南京市外国语学校,江江苏苏,中国中国February 4,2023Zeyuan Zhu5New algorithm for Half-plane Intersection and its Practical Value Thesis for Chinese Team Selecting Contest 2006 半平面交的新算法及其实用价值半平面交的新算法及其实用价值 中国代表队中国代表队2006年选拔赛论文年选拔赛论文Zeyuan Zhu,Grade 12,Nanjing Foreign Language School

5、,Jiangsu,China.朱泽园朱泽园,高三高三,南京市外国语学校南京市外国语学校,江江苏苏,中国中国February 4,2023Zeyuan Zhu6Project Overview 全文总揽全文总揽Aim:Present a new O(nlogn)algorithm for half-plane intersection(abbr.HPI),which is one of the most heatedly discussed problems in computer science;emphasize its advantages in practical application

6、,and to some extent,reduce the complexity to O(n).However,the new algorithm will be extraordinarily easy to be implemented.主旨主旨:半平面的交是当今学术界热烈讨论的问半平面的交是当今学术界热烈讨论的问题之一，本文将介绍一个全新的题之一，本文将介绍一个全新的O(nlogn)半平半平面交算法，强调它在实际运用中的价值，并且面交算法，强调它在实际运用中的价值，并且在某种程度上将复杂度下降至在某种程度上将复杂度下降至O(n)线性。最重线性。最重要的是，我将介绍的算法非常便于实现要

7、的是，我将介绍的算法非常便于实现.February 4,2023Zeyuan Zhu7Project Overview 全文总揽全文总揽1 introduces what Half-Plane Intersection(HPI)is.什么是半平面交什么是半平面交.2 prepares a convex polygon intersection(CPI).凸多边形交预备知识凸多边形交预备知识.3 briefly discuss a common solution for HPI D&C.简要介绍旧简要介绍旧D&C算法算法.4 my new algorithm S&I emerges detail

8、edly.揭开我的新算法揭开我的新算法S&I神秘面纱神秘面纱.5 conclusion and discussion on further practical use.总结和实际运用总结和实际运用.February 4,2023Zeyuan Zhu81.Statement of the Problem-问题概述问题概述February 4,2023Zeyuan Zhu91.Statement of the Problem A line in plane is usually represented as ax+by=c.Similarly,its inequality form ax+by (

9、)c represents a half-plane(also named h-plane for short)as one side of this line.3x-2y=1x+2y 1众所周知，直线常用众所周知，直线常用ax+by=c表示，表示，类似地半平面以类似地半平面以ax+by ()c为定义。为定义。February 4,2023Zeyuan Zhu101.Statement of the Problem Given n half-planes,aix+biy ci(1 i n),you are to determine the set of all points that sati

10、sfying all the n inequations.给定给定n个形如个形如aix+biy ci的半平面，找的半平面，找到所有满足它们的点所组成的点集到所有满足它们的点所组成的点集February 4,2023Zeyuan Zhu111.Statement of the Problem Feasible region forms a shape of convex hull possibly unbounded.Add four h-planes forming a rectangle,to make the intersection area finite.合并后区域形如凸多边形，可能无

11、界合并后区域形如凸多边形，可能无界此时增加此时增加4个半平面保证面积有限个半平面保证面积有限February 4,2023Zeyuan Zhu121.Statement of the Problem Each h-plane builds up at most one side of the convex polygon.Hence,The convex region will be bounded by at most n edges.每个半平面最多形成相交区域的一条每个半平面最多形成相交区域的一条边，因此相交区域不超过边，因此相交区域不超过n条边。条边。6 h-planespentagon

12、9 h-planespentagonFebruary 4,2023Zeyuan Zhu131.Statement of the Problem Pay attention that intersection sometimes yields a line,a ray,a line-segment,a point or an empty region.注意相交后的区域，有可能是一个直注意相交后的区域，有可能是一个直线、射线、线段或者点，当然也可能线、射线、线段或者点，当然也可能是空集。是空集。linerayline-segmentpointempty setFebruary 4,2023Zeyu

13、an Zhu142.Convex Polygon Intersection CPI凸多边形交预备知识凸多边形交预备知识February 4,2023Zeyuan Zhu152.Convex Polygon IntersectionIntersecting two convex polygons A and B into a single one.We will sketch out an efficient way,named plane sweep method.求两个凸多边求两个凸多边形形A和和B的交的交（一个新凸多（一个新凸多边形）。边形）。我们描绘一个我们描绘一个平面扫描法平面扫描法。

14、Polygon APolygon BFebruary 4,2023Zeyuan Zhu162.Convex Polygon IntersectionMain idea:Regard intersections of edges as cutting points,and break boundaries of A and B,into outer edges and inner edges.Segments of inner edges establish ties to each other,and form a polygon.(in bold)主要思想主要思想:以两凸以两凸边形边的交点为

15、边形边的交点为分界点，将边分分界点，将边分为内、外两种。为内、外两种。内边互相连接，内边互相连接，成为所求多边形成为所求多边形（图中粗线条）（图中粗线条）Polygon APolygon BFebruary 4,2023Zeyuan Zhu172.Convex Polygon IntersectionSuppose there is a vertical sweep line,performing left-to-right sweep.At anytime,there are at most four intersections from sweep line to either given

16、 polygon.假设有一个垂假设有一个垂直的扫描线，直的扫描线，从左向右扫描从左向右扫描任何时刻，扫任何时刻，扫描线和两个多描线和两个多边形最多边形最多4个交个交点点Polygon APolygon BBuAuBlAlSweep lineFebruary 4,2023Zeyuan Zhu182.Convex Polygon Intersectionthe lower one between Au and Bu,and the upper one between Al and Bl,form an interval of the current inner region the red seg

17、ment in bold.Au、Bu中靠下中靠下的，和的，和Al、Bl中靠上的，组中靠上的，组成了当前多边成了当前多边形的内部区域形的内部区域Polygon APolygon BBuAuBlAlSweep lineFebruary 4,2023Zeyuan Zhu192.Convex Polygon IntersectionLet us call the x-coordinates to be swept x-events.Obviously,the sweep line may not go through all the x-event with rational coordinates!

18、我们称被扫描我们称被扫描线扫描到的线扫描到的x坐坐标叫做标叫做x事件。事件。当然，我们不当然，我们不能扫描所有有能扫描所有有理数！理数！BuAuBlAlFebruary 4,2023Zeyuan Zhu202.Convex Polygon IntersectionCall the edges where Au,Al,Bu and Bl are:e1,e2,e3 and e4 respectively.Next x-event should be chosen among four endpoints of e1,e2,e3 and e4,and four potential intersect

19、ions:e1e3,e1e4,e2e3 and e2e4.称称Au,Al,Bu,Bl所在的边叫所在的边叫做做e1,e2,e3,e4下一个下一个x事件将事件将在这四条边的在这四条边的端点，以及两端点，以及两两交点中选出两交点中选出BuAuBlAlO(n)February 4,2023Zeyuan Zhu213.Common solution:Divide-and-Conquer Algorithm D&C通常的分治解法通常的分治解法February 4,2023Zeyuan Zhu223.Divide-and-Conquer Algorithm Divide:Partition the n h-

20、planes into two sets of size n/2.Conquer:Compute feasible region recursively of both two subsets.Combine:Compute intersection of two convex region,by CPI2分分:将将n个半平面分成两个个半平面分成两个n/2的集合的集合.治治:对两子集合递归求解半平面交对两子集合递归求解半平面交.合合:将前一步算出来的两个交将前一步算出来的两个交(凸多边凸多边形形)利用第利用第2章的章的CPI求解求解.February 4,2023Zeyuan Zhu233.D

21、ivide-and-Conquer Algorithm The total time complexity of the solution can be calculated via recursive equation.总时间复杂度可以用递归分析法总时间复杂度可以用递归分析法.2()2()()()(log)nT nTO nT nO nnCPIFebruary 4,2023Zeyuan Zhu244.My New Solution:Sort-and-Incremental Algorithm S&I我自创的排序增量算法我自创的排序增量算法February 4,2023Zeyuan Zhu254

22、.Sort-and-Incremental AlgorithmDefinition of h-planes polar angle:for h-plane like x-y constant,we define its polar angle to.半平面的极角定义半平面的极角定义:比如比如x-y 常数的半平常数的半平面，定义它的极角为面，定义它的极角为.-February 4,2023Zeyuan Zhu264.Sort-and-Incremental AlgorithmStep 1:Separate the h-planes into two sets.One has polar angl

23、es of(-,the other has those of(-,-(,.Step 1:将半平面分成两部分，一部将半平面分成两部分，一部分极角范围分极角范围(-,，另一部分范，另一部分范围围(-,-(,February 4,2023Zeyuan Zhu274.Sort-and-Incremental Algorithm考虑考虑(-,的半平的半平面面(另一个集合类似地做另一个集合类似地做Step3/4)，将他们极角，将他们极角排序排序。对极角相同的半。对极角相同的半平面，根据常数项保留平面，根据常数项保留其中之一。其中之一。Step 2:Consider the set of h-planes

24、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-planesFebruary 4,2023Zeyuan Zhu284.Sort-and-Incremental Algorithm从排序后极角最小两个从排序后极

25、角最小两个半平面开始，求出它们半平面开始，求出它们的交点并且将他们押入的交点并且将他们押入栈。栈。Step 3:Starting from two h-planes with the least polar angle,compute their intersection.Push them two into a stack.February 4,2023Zeyuan Zhu294.Sort-and-Incremental Algorithm每次按照极角从小到大每次按照极角从小到大顺序增加一个半平面，顺序增加一个半平面，算出它与栈顶半平面的算出它与栈顶半平面的交点。交点。Step 3:Each

26、 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.February 4,2023Zeyuan Zhu304.Sort-and-Incremental Algorithm如果当前的交点在栈顶如果当前的交点在栈顶两个半平面交点的右边，两个半平面交点的右边，出栈（出栈（pop）。）。Step 3:If this intersection is to the right of the inters

27、ection of top two h-planes in stack,we pop the stack once.February 4,2023Zeyuan Zhu314.Sort-and-Incremental AlgorithmStep 3:February 4,2023Zeyuan Zhu324.Sort-and-Incremental Algorithm前问我们说到出栈，出前问我们说到出栈，出栈只需要一次么？栈只需要一次么？Nie!我们要继续交点检查，我们要继续交点检查，如果还在右边我们要继如果还在右边我们要继续出栈，直到续出栈，直到当前交点当前交点在栈顶交点的左边在栈顶交点的左边。

28、Step 3:we pop the stack once.Once?Is it enough?Nie!Do this repeatedly until it is to the left of the top intersection.February 4,2023Zeyuan Zhu334.Sort-and-Incremental Algorithm相邻半平面的交点组成相邻半平面的交点组成半个凸多边形。我们有半个凸多边形。我们有两个点集，两个点集，(-,给出上半个，给出上半个，(-,-(,给出下给出下半个半个 Step 4:Intersections of adjacent h-plane

29、pairs in stack form half a convex polygon.For the two sets,we have two halves (-,gives an upper hull and(-,-(,gives a lower hull.February 4,2023Zeyuan Zhu344.Sort-and-Incremental Algorithm相邻半平面的交点组成相邻半平面的交点组成半个凸多边形。我们有半个凸多边形。我们有两个点集，两个点集，(-,给出上半个，给出上半个，(-,-(,给出下给出下半个半个 Step 4:Intersections of adjace

30、nt h-plane pairs in stack form half a convex polygon.For the two sets,we have two halves (-,gives an upper hull and(-,-(,gives a lower hull.upper hull上壳上壳lower hull下壳下壳February 4,2023Zeyuan Zhu354.Sort-and-Incremental Algorithm初始时候，四个指针初始时候，四个指针p1,p2,p3 and p4 指向指向上上/下凸壳的最左最右边下凸壳的最左最右边p1,p3向右走，向右走，p

31、2,p4向左走向左走Step 4:At the beginning,four pointers p1,p2,p3 and p4 indicate leftmost/rightmost edges of both upper and lower hulls.p1 and p3 move rightwards,while p2 and p4 walks leftwards.p3p4p1p2upper hull上壳上壳lower hull下壳下壳February 4,2023Zeyuan Zhu364.Sort-and-Incremental Algorithm任意时刻，如果最左边任意时刻，如果最左

32、边的交点不满足的交点不满足p1/p3所所在半平面的限制，我们在半平面的限制，我们相信这个交点需要删除相信这个交点需要删除p1或或p3走向它右边的走向它右边的相邻边相邻边Step 4:At anytime,if the leftmost intersection is against the feasible region provided by p1 or p3,we are sure the leftmost one is to be removed.Naturally,p1 or p3 walks rightwards to its adjacent edge.p3p4p1p2Februa

33、ry 4,2023Zeyuan Zhu374.Sort-and-Incremental Algorithm类似地我们处理最右边类似地我们处理最右边的交点的交点Step 4:The judgment holds analogously for rightmost intersection with p2 and p4.p3p2p1p4February 4,2023Zeyuan Zhu384.Sort-and-Incremental Algorithm类似地我们处理最右边类似地我们处理最右边的交点的交点Step 4:The judgment holds analogously for rightm

34、ost intersection with p2 and p4.p3p4p2p1February 4,2023Zeyuan Zhu394.Sort-and-Incremental Algorithm重复运作直到不再有更重复运作直到不再有更新出现新出现迭代迭代Step 4:Do the above removing repeatedly until there is no more update.p3p4p2p1February 4,2023Zeyuan Zhu404.Sort-and-Incremental Algorithm Everything except sorting(Step 2)

35、in S&I algorithm remain linear O(n)running time.Usually we use quick-sort.The total complexity is O(nlogn),with fairly small constant factor hidden.除了除了Step2中的排序以外，中的排序以外，S&I算法的算法的每一步都是线性的。通常我们用快速每一步都是线性的。通常我们用快速排序实现排序实现Step2，总的时间复杂度为，总的时间复杂度为O(nlogn)，隐蔽其中的，隐蔽其中的常数因子常数因子很小很小February 4,2023Zeyuan Zhu

36、415.Conclusion and Practical Use总结和实际应用总结和实际应用February 4,2023Zeyuan Zhu425.Conclusion and Practical UseGreat ideas need landing gear as well as wings.S&I algorithm seems to work in the same time complexity as D&C algorithm,but some overwhelming advantages of implementing S&I holds.Great ideas need l

37、anding gear as well as wings.S&I算法似乎和算法似乎和D&C算法时间复杂度相同，但是它有着压算法时间复杂度相同，但是它有着压倒性倒性(overwhelming)的优势。的优势。February 4,2023Zeyuan Zhu435.Conclusion and Practical UseIt is much easier to code S&I program than D&C one.The program in C+programming language takes less than 3KB.新的新的S&I算法代码容易编写，相对于算法代码容易编写，相对于

38、D&C大大简单化，大大简单化，C+程序语言实现程序语言实现S&I算法仅需算法仅需3KB不到不到.February 4,2023Zeyuan Zhu445.Conclusion and Practical UseThe coefficient hidden under S&I algorithms complexity is extraordinarily smaller than D&C,since we no longer need O(nlogn)number of intersection calculates.In general speaking,S&I program runs a

39、pprox five times faster than D&C one.S&I算法复杂度中的系数，远小于算法复杂度中的系数，远小于D&C，因为我们不再需要，因为我们不再需要O(nlogn)次次交点运算交点运算.通常意义上来讲，通常意义上来讲，S&I程序程序比比D&C快五倍。快五倍。February 4,2023Zeyuan Zhu455.Conclusion and Practical UseIf the given h-planes are all in(-,(or any span of),S&I program can be shorten remarkably(to approxim

40、ately twenty lines in C+),but D&C program may not.An informatics problem ap p eared i n US A I n vi tat i o n a l Computing Olympiad contest with such purpose.如果给定半平面均在如果给定半平面均在(-,（或任意一（或任意一个跨度为个跨度为的区间），的区间），S&I算法可被显著缩算法可被显著缩短，短，C+程序只需要约二十行。程序只需要约二十行。USAICO比比赛中就出现了这样一题。赛中就出现了这样一题。February 4,2023Zeyu

41、an Zhu465.Conclusion and Practical UseThe bottleneck of this algorithm is sorting.Pay attention the sorting is NOT a comparison sort(sorting based on comparison)!Since then,we can replace the O(nlogn)quick-sort to O(n)radix-sort to decrease the asymptotical time complexity to O(n).本算法瓶颈是排序，这里的排序不是比较

42、本算法瓶颈是排序，这里的排序不是比较排序，因此可以将快速排序替换成基数排排序，因此可以将快速排序替换成基数排序，序，降低程序渐进时间复杂度到线性降低程序渐进时间复杂度到线性。Anyway O(n)approach usually runs slower than nlogn ones for its additional memory usage!February 4,2023Zeyuan Zhu475.Conclusion and Practical Use诺贝尔奖得主诺贝尔奖得主John Nash原创的理论原创的理论original idea创新与信息学竞赛创新与信息学竞赛创新与技术创新与

43、技术我心目中的创新我心目中的创新最重要的是最重要的是思想思想创新，其次是创新，其次是行为行为创新，再其次是文创新，再其次是文章创新，再再其次才是语言创新章创新，再再其次才是语言创新思想思想实践实践The principal mark of genius is not perfection but originality,the opening of new frontiers.Authur Koestler(1905-1983)Hungarian-born British writer and jounalist.February 4,2023Zeyuan Zhu485.Conclusion and Practical Use创新如高山创新如高山山，山，快马加鞭未下鞍。快马加鞭未下鞍。惊回首，离天三尺三。惊回首，离天三尺三。山，山，倒海翻江卷巨澜。倒海翻江卷巨澜。奔腾急，万马战犹酣。奔腾急，万马战犹酣。山，山，刺破青天锷未残。刺破青天锷未残。天欲堕，赖以拄其间。天欲堕，赖以拄其间。怅寥廓，问苍茫大地，谁主沉浮。怅寥廓，问苍茫大地，谁主沉浮。俱往矣，数风流人物，还看今朝。俱往矣，数风流人物，还看今朝。