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

《算法合集之《半平面交的新算法及其实用价值》课件》由会员分享，可在线阅读，更多相关《算法合集之《半平面交的新算法及其实用价值》课件（48页珍藏版）》请在装配图网上搜索。

1、Hello,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 School,Jiangsu,China.朱泽园朱泽园,高三高三,南京市外国语学校南京市外国语学校,江苏江苏,中国中国4/16/20234Zeyuan

2、ZhuNew 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,Jiangsu,China.朱泽园朱泽园,高三高三,南京市外国语学校南京市外国语学校,江苏江苏,中国中国4/16/20235Zeyuan ZhuProje

3、ct 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,and to some extent,reduce the complexity to O(n).However,the new algorithm will be

4、extraordinarily easy to be implemented.主旨主旨:半平面的交是当今学术界热烈讨论的问半平面的交是当今学术界热烈讨论的问题之一，本文将介绍一个全新的题之一，本文将介绍一个全新的O(nlogn)半平半平面交算法，强调它在实际运用中的价值，并且面交算法，强调它在实际运用中的价值，并且在某种程度上将复杂度下降至在某种程度上将复杂度下降至O(n)线性。最重线性。最重要的是，我将介绍的算法非常便于实现要的是，我将介绍的算法非常便于实现.4/16/20236Zeyuan ZhuProject Overview 全文总揽全文总揽1 introduces what Half

5、-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 detailedly.揭开我的新算法揭开我的新算法S&I神秘面纱神秘面纱.5 conclusion and discussion on further practical use.总结和实际运

6、用总结和实际运用.4/16/20237Zeyuan Zhu1.Statement of the Problem-问题概述问题概述4/16/20238Zeyuan Zhu1.Statement of the Problem A line in plane is usually represented as ax+by=c.Similarly,its inequality form ax+by ()c represents a half-plane(also named h-plane for short)as one side of this line.3x-2y=1x+2y 1众所周知，直线常

7、用众所周知，直线常用ax+by=c表示，表示，类似地半平面以类似地半平面以ax+by ()c为定义。为定义。4/16/20239Zeyuan Zhu1.Statement of the Problem Given n half-planes,aix+biy ci(1 i n),you are to determine the set of all points that satisfying all the n inequations.给定给定n个形如个形如aix+biy ci的半平面，找的半平面，找到所有满足它们的点所组成的点集到所有满足它们的点所组成的点集4/16/202310Zeyuan

8、 Zhu1.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.合并后区域形如凸多边形，可能无界合并后区域形如凸多边形，可能无界此时增加此时增加4个半平面保证面积有限个半平面保证面积有限4/16/202311Zeyuan Zhu1.Statement of the Problem Pay attention that in

9、tersection sometimes yields a line,a ray,a line-segment,a point or an empty region.注意相交后的区域，有可能是一个直注意相交后的区域，有可能是一个直线、射线、线段或者点，当然也可能线、射线、线段或者点，当然也可能是空集。是空集。linerayline-segmentpointempty set4/16/202313Zeyuan Zhu2.Convex Polygon Intersection CPI凸多边形交预备知识凸多边形交预备知识4/16/202314Zeyuan Zhu2.Convex Polygon In

10、tersectionIntersecting two convex polygons A and B into a single one.We will sketch out an efficient way,named plane sweep method.求两个凸多边形求两个凸多边形A和和B的交（一的交（一个新凸多边形）。个新凸多边形）。我们描绘一个我们描绘一个平平面扫描法面扫描法。Polygon APolygon B4/16/202315Zeyuan Zhu2.Convex Polygon IntersectionMain idea:Regard intersections of edg

11、es 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)主要思想主要思想:以两凸以两凸边形边的交点为分边形边的交点为分界点，将边分为内界点，将边分为内、外两种。、外两种。内边互相连接，成内边互相连接，成为所求多边形（图为所求多边形（图中粗线条）中粗线条）Polygon APolygon B4/16/202316Zeyua

12、n Zhu2.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 polygon.假设有一个垂直假设有一个垂直的扫描线，从左的扫描线，从左向右扫描向右扫描任何时刻，扫描任何时刻，扫描线和两个多边形线和两个多边形最多最多4个交点个交点Polygon APolygon BBuAuBlAlSweep l

13、ine4/16/202317Zeyuan Zhu2.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 segment in bold.Au、Bu中靠下中靠下的，和的，和Al、Bl中中靠上的，组成了靠上的，组成了当前多边形的内当前多边形的内部区域部区域Polygon APolygon BBuAuBlAlSweep line4/16/202318Zeyua

14、n Zhu2.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!我们称被扫描线我们称被扫描线扫描到的扫描到的x坐标坐标叫做叫做x事件。事件。当然，我们不能当然，我们不能扫描所有有理数扫描所有有理数！BuAuBlAl4/16/202319Zeyuan Zhu2.Convex Polygon IntersectionCall

15、 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 intersections:e1e3,e1e4,e2e3 and e2e4.称称Au,Al,Bu,Bl所在的边叫做所在的边叫做e1,e2,e3,e4下一个下一个x事件将事件将在这四条边的端在这四条边的端点，以及两两交点，以及两两交点中选出点中选出BuAuBlAlO(n)4/16/20232

16、0Zeyuan Zhu3.Common solution:Divide-and-Conquer Algorithm D&C通常的分治解法通常的分治解法4/16/202321Zeyuan Zhu3.Divide-and-Conquer Algorithm Divide:Partition the n h-planes into two sets of size n/2.Conquer:Compute feasible region recursively of both two subsets.Combine:Compute intersection of two convex region,b

17、y CPI2分分:将将n个半平面分成两个个半平面分成两个n/2的集合的集合.治治:对两子集合递归求解半平面交对两子集合递归求解半平面交.合合:将将前前一一步步算算出出来来的的两两个个交交(凸凸多多边边形形)利用第利用第2章的章的CPI求解求解.4/16/202322Zeyuan Zhu3.Divide-and-Conquer Algorithm The total time complexity of the solution can be calculated via recursive equation.总时间复杂度可以用递归分析法总时间复杂度可以用递归分析法.CPI4/16/202323

18、Zeyuan Zhu4.My New Solution:Sort-and-Incremental Algorithm S&I我自创的排序增量算法我自创的排序增量算法4/16/202324Zeyuan Zhu4.Sort-and-Incremental AlgorithmDefinition of h-planes polar angle:for h-plane like x-y constant,we define its polar angle to.半平面的极角定义半平面的极角定义:比如比如x-y 常数的半平常数的半平面，定义它的极角为面，定义它的极角为.-4/16/202325Zeyua

19、n Zhu4.Sort-and-Incremental AlgorithmStep 1:Separate the h-planes into two sets.One has polar angles of(-,the other has those of(-,-(,.Step 1:将半平面分成两部分，一部将半平面分成两部分，一部分极角范围分极角范围(-,，另一部分范，另一部分范围围(-,-(,4/16/202326Zeyuan Zhu4.Sort-and-Incremental Algorithm考虑考虑(-,的半的半平面平面(另一个集合类似另一个集合类似地做地做Step3/4)，将他们，将

20、他们极角极角排序排序。对极角相同。对极角相同的半平面，根据常数项的半平面，根据常数项保留其中之一。保留其中之一。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

21、 of these h-planes4/16/202327Zeyuan Zhu4.Sort-and-Incremental Algorithm从排序后极角最小两个从排序后极角最小两个半平面开始，求出它们半平面开始，求出它们的交点并且将他们押入的交点并且将他们押入栈。栈。Step 3:Starting from two h-planes with the least polar angle,compute their intersection.Push them two into a stack.4/16/202328Zeyuan Zhu4.Sort-and-Incremental Algori

22、thm每次按照极角从小到大每次按照极角从小到大顺序增加一个半平面，顺序增加一个半平面，算出它与栈顶半平面的算出它与栈顶半平面的交点。交点。Step 3: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.4/16/202329Zeyuan Zhu4.Sort-and-Incremental Algorithm如果当前的交点在栈顶如果当前的交点在栈顶两个半平面交点的右边，两个半平面交点

23、的右边，出栈（出栈（pop）。）。Step 3:If this intersection is to the right of the intersection of top two h-planes in stack,we pop the stack once.4/16/202330Zeyuan Zhu4.Sort-and-Incremental AlgorithmStep 3:4/16/202331Zeyuan Zhu4.Sort-and-Incremental Algorithm前问我们说到出栈，出前问我们说到出栈，出栈只需要一次么？栈只需要一次么？Nie!我们要继续交点检查，我们要继续

24、交点检查，如果还在右边我们要继如果还在右边我们要继续出栈，直到续出栈，直到当前交点当前交点在栈顶交点的左边在栈顶交点的左边。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.4/16/202332Zeyuan Zhu4.Sort-and-Incremental Algorithm相邻半平面的交点组成相邻半平面的交点组成半个凸多边形。我们有半个凸多边形。我们有两个点集，两个点集，(-,给出上半个，给出上半个，(-

25、,-(,给出下给出下半个半个 Step 4:Intersections of adjacent 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.4/16/202333Zeyuan Zhu4.Sort-and-Incremental Algorithm相邻半平面的交点组成相邻半平面的交点组成半个凸多边形。我们有半个凸多边形。我们有两个点集，两个点集，(-,给出上半个，给出上

26、半个，(-,-(,给出下给出下半个半个 Step 4:Intersections of adjacent 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下壳下壳4/16/202334Zeyuan Zhu4.Sort-and-Incremental Algorithm初始时候，四个指针初始时候，四个指针p1,p2,p3 an

27、d p4 指向指向上上/下凸壳的最左最右下凸壳的最左最右边边p1,p3向右走，向右走，p2,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下壳下壳4/16/202335Zeyuan Zhu4.Sort-and-In

28、cremental Algorithm任意时刻，如果最左边任意时刻，如果最左边的交点不满足的交点不满足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 rightwar

29、ds to its adjacent edge.p3p4p1p24/16/202336Zeyuan Zhu4.Sort-and-Incremental Algorithm类似地我们处理最右边类似地我们处理最右边的交点的交点Step 4:The judgment holds analogously for rightmost intersection with p2 and p4.p3p2p1p44/16/202337Zeyuan Zhu4.Sort-and-Incremental Algorithm类似地我们处理最右边类似地我们处理最右边的交点的交点Step 4:The judgment ho

30、lds analogously for rightmost intersection with p2 and p4.p3p4p2p14/16/202338Zeyuan Zhu4.Sort-and-Incremental Algorithm重复运作直到不再有更重复运作直到不再有更新出现新出现迭代迭代Step 4:Do the above removing repeatedly until there is no more update.p3p4p2p14/16/202339Zeyuan Zhu4.Sort-and-Incremental AlgorithmEverything except so

31、rting(Step 2)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)，隐蔽其中的，隐蔽其中的常数因子常数因子很小很小4/16/202340Z

32、eyuan Zhu5.Conclusion and Practical Use总结和实际应用总结和实际应用4/16/202341Zeyuan Zhu5.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

33、landing gear as well as wings.S&I算算法法似似乎乎和和D&C算算法法时时间间复复杂杂度度相相同同，但但是是它它有有着着压压倒性倒性(overwhelming)的优势。的优势。4/16/202342Zeyuan Zhu5.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算算法法代代码码容容易易编编写写，相相对对于于D&C大大大大

34、简简单单化化，C+程程序序语语言言实实现现S&I算法仅需算法仅需3KB不到不到.4/16/202343Zeyuan Zhu5.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 approx five tim

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

36、+),but D&C program may not.An informatics problem appeared in USA Invitational Computing Olympiad contest with such purpose.如如果果给给定定半半平平面面均均在在(-,（或或任任意意一一个个跨跨度度为为的的区区间间），S&I算算法法可可被被显显著著缩缩短短，C+程程序序只只需需要要约约二二十十行行。USAICO比赛中就出现了这样一题。比赛中就出现了这样一题。4/16/202345Zeyuan Zhu5.Conclusion and Practical UseThe bott

37、leneck 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).本本算算法法瓶瓶颈颈是是排排序序，这这里里的的排排序序不不是是比比较较排排序序，因因此此可可以以将将快快速速排排序序替替换换成成

38、基基数数排排序，序，降低程序渐进时间复杂度到线性降低程序渐进时间复杂度到线性。Anyway O(n)approach usually runs slower than nlogn ones for its additional memory usage!4/16/202346Zeyuan Zhu5.Conclusion and Practical Use诺诺贝贝尔尔奖奖得得主主John Nash原创的理论原创的理论original idea创新与信息学竞赛创新与信息学竞赛创新与技术创新与技术我我心心目目中中的的创创新新最最重重要要的的是是思思想想创创新新，其其次次是是行行为为创创新新，再再其其

39、次次是是文文章创新，再再其次才是语言创新章创新，再再其次才是语言创新思想思想实践实践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.4/16/202347Zeyuan Zhu5.Conclusion and Practical Use创新如高山创新如高山山，山，快马加鞭未下鞍。快马加鞭未下鞍。惊回首，离天三尺三。惊回首，离天三尺三。山，山，倒海翻江卷巨澜。倒海翻江卷巨澜。奔腾急，万马战犹酣。奔腾急，万马战犹酣。山，山，刺破青天锷未残。刺破青天锷未残。天欲堕，赖以拄其间。天欲堕，赖以拄其间。怅怅寥寥廓廓，问问苍苍茫茫大大地地，谁谁主主沉沉浮浮。俱俱往往矣矣，数数风风流流人人物物，还还看看今今朝朝。4/16/202348Zeyuan Zhu