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

February10 2020 ZeyuanZhu 1 Allgreatideasarecontroversial orhavebeenatonetime 伟大的理论都是有争议的 或者至少曾经是有争议的 GilbertSeldes 1893 1970 U S theater film andradiocritic 理论的争议 February10 2020 ZeyuanZhu 2 Awisemanwillmakemoreopportunitiesthanhefinds 聪明人总是制造更多的机会 而不是去等待寻找 FrancisBacon 1561 1626 Englishphilosopher statesman andlawyer 制造机会 February10 2020 ZeyuanZhu 3 Aftertheleaveshavefallen wereturntoaplainsenseofthings Itisasifwehadcometoanendoftheimagination 叶落时分 我们回到一切的本来面目 这样就与创造与幻想的终点不远了 WallaceStevens 1879 1955 U S poet 忘记过去 揭开本来面目 February10 2020 ZeyuanZhu 4 Hello LadiesandGentlemen 女士们先生们大家好Bonjour MesdamesetMessieurs Witajcie PanieiPanowie Hallo DamenundHerren Bunaziua DoamenelorsiDomnilor Ciao signoreesignori ZeyuanZhu Grade12 NanjingForeignLanguageSchool Jiangsu China 朱泽园 高三 南京市外国语学校 江苏 中国 February10 2020 ZeyuanZhu 5 NewalgorithmforHalf planeIntersectionanditsPracticalValue ThesisforChineseTeamSelectingContest2006半平面交的新算法及其实用价值 中国代表队2006年选拔赛论文 ZeyuanZhu Grade12 NanjingForeignLanguageSchool Jiangsu China 朱泽园 高三 南京市外国语学校 江苏 中国 February10 2020 ZeyuanZhu 6 ProjectOverview 全文总揽 Aim PresentanewO nlogn algorithmforhalf planeintersection abbr HPI whichisoneofthemostheatedlydiscussedproblemsincomputerscience emphasizeitsadvantagesinpracticalapplication andtosomeextent reducethecomplexitytoO n However thenewalgorithmwillbeextraordinarilyeasytobeimplemented 主旨 半平面的交是当今学术界热烈讨论的问题之一 本文将介绍一个全新的O nlogn 半平面交算法 强调它在实际运用中的价值 并且在某种程度上将复杂度下降至O n 线性 最重要的是 我将介绍的算法非常便于实现 February10 2020 ZeyuanZhu 7 ProjectOverview 全文总揽 1introduceswhatHalf PlaneIntersection HPI is 什么是半平面交 2preparesaconvexpolygonintersection CPI 凸多边形交预备知识 3brieflydiscussacommonsolutionforHPI D C 简要介绍旧D C算法 4mynewalgorithmS Iemergesdetailedly 揭开我的新算法S I神秘面纱 5conclusionanddiscussiononfurtherpracticaluse 总结和实际运用 February10 2020 ZeyuanZhu 8 1 StatementoftheProblem 问题概述 February10 2020 ZeyuanZhu 9 1 StatementoftheProblem Alineinplaneisusuallyrepresentedasax by c Similarly itsinequalityformax by crepresentsahalf plane alsonamedh planeforshort asonesideofthisline 3x 2y 1 x 2y 1 众所周知 直线常用ax by c表示 类似地半平面以ax by c为定义 February10 2020 ZeyuanZhu 10 1 StatementoftheProblem Givennhalf planes aix biy ci 1 i n youaretodeterminethesetofallpointsthatsatisfyingalltheninequations 给定n个形如aix biy ci的半平面 找到所有满足它们的点所组成的点集 February10 2020 ZeyuanZhu 11 1 StatementoftheProblem Feasibleregionformsashapeofconvexhullpossiblyunbounded Addfourh planesformingarectangle tomaketheintersectionareafinite 合并后区域形如凸多边形 可能无界此时增加4个半平面保证面积有限 February10 2020 ZeyuanZhu 12 1 StatementoftheProblem Eachh planebuildsupatmostonesideoftheconvexpolygon Hence Theconvexregionwillbeboundedbyatmostnedges 每个半平面最多形成相交区域的一条边 因此相交区域不超过n条边 6h planespentagon 9h planespentagon February10 2020 ZeyuanZhu 13 1 StatementoftheProblem Payattentionthatintersectionsometimesyieldsaline aray aline segment apointoranemptyregion 注意相交后的区域 有可能是一个直线 射线 线段或者点 当然也可能是空集 line ray line segment point emptyset February10 2020 ZeyuanZhu 14 2 ConvexPolygonIntersection CPI凸多边形交预备知识 February10 2020 ZeyuanZhu 15 2 ConvexPolygonIntersection IntersectingtwoconvexpolygonsAandBintoasingleone Wewillsketchoutanefficientway namedplanesweepmethod 求两个凸多边形A和B的交 一个新凸多边形 我们描绘一个平面扫描法 PolygonA PolygonB February10 2020 ZeyuanZhu 16 2 ConvexPolygonIntersection Mainidea Regardintersectionsofedgesascuttingpoints andbreakboundariesofAandB intoouteredgesandinneredges Segmentsofinneredgesestablishtiestoeachother andformapolygon inbold 主要思想 以两凸边形边的交点为分界点 将边分为内 外两种 内边互相连接 成为所求多边形 图中粗线条 PolygonA PolygonB February10 2020 ZeyuanZhu 17 2 ConvexPolygonIntersection Supposethereisaverticalsweepline performingleft to rightsweep Atanytime thereareatmostfourintersectionsfromsweeplinetoeithergivenpolygon 假设有一个垂直的扫描线 从左向右扫描任何时刻 扫描线和两个多边形最多4个交点 PolygonA PolygonB Bu Au Bl Al Sweepline February10 2020 ZeyuanZhu 18 2 ConvexPolygonIntersection theloweronebetweenAuandBu andtheupperonebetweenAlandBl formanintervalofthecurrentinnerregion theredsegmentinbold Au Bu中靠下的 和Al Bl中靠上的 组成了当前多边形的内部区域 PolygonA PolygonB Bu Au Bl Al Sweepline February10 2020 ZeyuanZhu 19 2 ConvexPolygonIntersection Letuscallthex coordinatestobesweptx events Obviously thesweeplinemaynotgothroughallthex eventwithrationalcoordinates 我们称被扫描线扫描到的x坐标叫做x事件 当然 我们不能扫描所有有理数 Bu Au Bl Al February10 2020 ZeyuanZhu 20 2 ConvexPolygonIntersection CalltheedgeswhereAu Al BuandBlare e1 e2 e3ande4respectively Nextx eventshouldbechosenamongfourendpointsofe1 e2 e3ande4 andfourpotentialintersections e1 e3 e1 e4 e2 e3ande2 e4 称Au Al Bu Bl所在的边叫做e1 e2 e3 e4下一个x事件将在这四条边的端点 以及两两交点中选出 Bu Au Bl Al O n February10 2020 ZeyuanZhu 21 3 Commonsolution Divide and ConquerAlgorithm D C通常的分治解法 February10 2020 ZeyuanZhu 22 3 Divide and ConquerAlgorithm Divide Partitionthenh planesintotwosetsofsizen 2 Conquer Computefeasibleregionrecursivelyofbothtwosubsets Combine Computeintersectionoftwoconvexregion byCPI 2分 将n个半平面分成两个n 2的集合 治 对两子集合递归求解半平面交 合 将前一步算出来的两个交 凸多边形 利用第2章的CPI求解 February10 2020 ZeyuanZhu 23 3 Divide and ConquerAlgorithm Thetotaltimecomplexityofthesolutioncanbecalculatedviarecursiveequation 总时间复杂度可以用递归分析法 February10 2020 ZeyuanZhu 24 4 MyNewSolution Sort and IncrementalAlgorithm S I我自创的排序增量算法 February10 2020 ZeyuanZhu 25 4 Sort and IncrementalAlgorithm Definitionofh plane spolarangle forh planelikex y constant wedefineitspolarangleto 半平面的极角定义 比如x y 常数的半平面 定义它的极角为 February10 2020 ZeyuanZhu 26 4 Sort and IncrementalAlgorithm Step1 Separatetheh planesintotwosets Onehaspolaranglesof theotherhasthoseof Step1 将半平面分成两部分 一部分极角范围 另一部分范围 February10 2020 ZeyuanZhu 27 4 Sort and IncrementalAlgorithm 考虑 的半平面 另一个集合类似地做Step3 4 将他们极角排序 对极角相同的半平面 根据常数项保留其中之一 Step2 Considerthesetofh planesin theothersetshouldalsogothroughstep3and4similarly Sortthembythepolarangle Fortheh planeswiththesamepolarangle wecankeeponlyonedown deleteallothers accordingtotheconstantoftheseh planes February10 2020 ZeyuanZhu 28 4 Sort and IncrementalAlgorithm 从排序后极角最小两个半平面开始 求出它们的交点并且将他们押入栈 Step3 Startingfromtwoh planeswiththeleastpolarangle computetheirintersection Pushthemtwointoastack February10 2020 ZeyuanZhu 29 4 Sort and IncrementalAlgorithm 每次按照极角从小到大顺序增加一个半平面 算出它与栈顶半平面的交点 Step3 Eachtime addonemoreh planebyincreasingorderofpolarangles andcalculatetheintersectionofitandthetoph planeinstack February10 2020 ZeyuanZhu 30 4 Sort and IncrementalAlgorithm 如果当前的交点在栈顶两个半平面交点的右边 出栈 pop Step3 Ifthisintersectionistotherightoftheintersectionoftoptwoh planesinstack wepopthestackonce February10 2020 ZeyuanZhu 31 4 Sort and IncrementalAlgorithm Step3 February10 2020 ZeyuanZhu 32 4 Sort and IncrementalAlgorithm 前问我们说到出栈 出栈只需要一次么 Nie 我们要继续交点检查 如果还在右边我们要继续出栈 直到当前交点在栈顶交点的左边 Step3 wepopthestackonce Once Isitenough Nie Dothisrepeatedlyuntilitistotheleftofthetopintersection February10 2020 ZeyuanZhu 33 4 Sort and IncrementalAlgorithm 相邻半平面的交点组成半个凸多边形 我们有两个点集 给出上半个 给出下半个 Step4 Intersectionsofadjacenth planepairsinstackformhalfaconvexpolygon Forthetwosets wehavetwohalves givesanupperhulland givesalowerhull February10 2020 ZeyuanZhu 34 4 Sort and IncrementalAlgorithm 相邻半平面的交点组成半个凸多边形 我们有两个点集 给出上半个 给出下半个 Step4 Intersectionsofadjacenth planepairsinstackformhalfaconvexpolygon Forthetwosets wehavetwohalves givesanupperhulland givesalowerhull upperhull上壳 lowerhull下壳 February10 2020 ZeyuanZhu 35 4 Sort and IncrementalAlgorithm 初始时候 四个指针p1 p2 p3andp4指向上 下凸壳的最左最右边p1 p3向右走 p2 p4向左走 Step4 Atthebeginning fourpointersp1 p2 p3andp4indicateleftmost rightmostedgesofbothupperandlowerhulls p1andp3moverightwards whilep2andp4walksleftwards p3 p4 p1 p2 upperhull上壳 lowerhull下壳 February10 2020 ZeyuanZhu 36 4 Sort and IncrementalAlgorithm 任意时刻 如果最左边的交点不满足p1 p3所在半平面的限制 我们相信这个交点需要删除p1或p3走向它右边的相邻边 Step4 Atanytime iftheleftmostintersectionisagainstthefeasibleregionprovidedbyp1orp3 wearesuretheleftmostoneistoberemoved Naturally p1orp3walksrightwardstoitsadjacentedge p3 p4 p1 p2 February10 2020 ZeyuanZhu 37 4 Sort and IncrementalAlgorithm 类似地我们处理最右边的交点 Step4 Thejudgmentholdsanalogouslyforrightmostintersectionwithp2andp4 p3 p2 p1 p4 February10 2020 ZeyuanZhu 38 4 Sort and IncrementalAlgorithm 类似地我们处理最右边的交点 Step4 Thejudgmentholdsanalogouslyforrightmostintersectionwithp2andp4 p3 p4 p2 p1 February10 2020 ZeyuanZhu 39 4 Sort and IncrementalAlgorithm 重复运作直到不再有更新出现 迭代 Step4 Dotheaboveremovingrepeatedlyuntilthereisnomoreupdate p3 p4 p2 p1 February10 2020 ZeyuanZhu 40 4 Sort and IncrementalAlgorithm Everythingexceptsorting Step2 inS Ialgorithmremainlinear O n runningtime Usuallyweusequick sort ThetotalcomplexityisO nlogn withfairlysmallconstantfactorhidden 除了Step2中的排序以外 S I算法的每一步都是线性的 通常我们用快速排序实现Step2 总的时间复杂度为O nlogn 隐蔽其中的常数因子很小 February10 2020 ZeyuanZhu 41 5 ConclusionandPracticalUse总结和实际应用 February10 2020 ZeyuanZhu 42 5 ConclusionandPracticalUse Greatideasneedlandinggearaswellaswings S IalgorithmseemstoworkinthesametimecomplexityasD Calgorithm butsomeoverwhelmingadvantagesofimplementingS Iholds Greatideasneedlandinggearaswellaswings S I算法似乎和D C算法时间复杂度相同 但是它有着压倒性 overwhelming 的优势 February10 2020 ZeyuanZhu 43 5 ConclusionandPracticalUse ItismucheasiertocodeS IprogramthanD Cone TheprograminC programminglanguagetakeslessthan3KB 新的S I算法代码容易编写 相对于D C大大简单化 C 程序语言实现S I算法仅需3KB不到 February10 2020 ZeyuanZhu 44 5 ConclusionandPracticalUse ThecoefficienthiddenunderS Ialgorithm scomplexityisextraordinarilysmallerthanD C sincewenolongerneedO nlogn numberofintersectioncalculates Ingeneralspeaking S IprogramrunsapproxfivetimesfasterthanD Cone S I算法复杂度中的系数 远小于D C 因为我们不再需要O nlogn 次交点运算 通常意义上来讲 S I程序比D C快五倍 February10 2020 ZeyuanZhu 45 5 ConclusionandPracticalUse Ifthegivenh planesareallin oranyspanof S Iprogramcanbesho