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

February10 2020 ZeyuanZhu 1 Allgreatideasarecontroversial orhavebeenatonetime 偉大的理論都是有爭議的 或者至少曾經(jīng)是有爭議的 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 葉落時分 我們回到一切的本來面目 這樣就與創(chuàng)造與幻想的終點不遠了 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 朱澤園 高三 南京市外國語學(xué)校 江蘇 中國 February10 2020 ZeyuanZhu 5 NewalgorithmforHalf planeIntersectionanditsPracticalValue ThesisforChineseTeamSelectingContest2006半平面交的新算法及其實用價值 中國代表隊2006年選拔賽論文 ZeyuanZhu Grade12 NanjingForeignLanguageSchool Jiangsu China 朱澤園 高三 南京市外國語學(xué)校 江蘇 中國 February10 2020 ZeyuanZhu 6 ProjectOverview 全文總攬 Aim PresentanewO nlogn algorithmforhalf planeintersection abbr HPI whichisoneofthemostheatedlydiscussedproblemsincomputerscience emphasizeitsadvantagesinpracticalapplication andtosomeextent reducethecomplexitytoO n However thenewalgorithmwillbeextraordinarilyeasytobeimplemented 主旨 半平面的交是當今學(xué)術(shù)界熱烈討論的問題之一 本文將介紹一個全新的O nlogn 半平面交算法 強調(diào)它在實際運用中的價值 并且在某種程度上將復(fù)雜度下降至O n 線性 最重要的是 我將介紹的算法非常便于實現(xiàn) February10 2020 ZeyuanZhu 7 ProjectOverview 全文總攬 1introduceswhatHalf PlaneIntersection HPI is 什么是半平面交 2preparesaconvexpolygonintersection CPI 凸多邊形交預(yù)備知識 3brieflydiscussacommonsolutionforHPI D C 簡要介紹舊D C算法 4mynewalgorithmS Iemergesdetailedly 揭開我的新算法S I神秘面紗 5conclusionanddiscussiononfurtherpracticaluse 總結(jié)和實際運用 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 合并后區(qū)域形如凸多邊形 可能無界此時增加4個半平面保證面積有限 February10 2020 ZeyuanZhu 12 1 StatementoftheProblem Eachh planebuildsupatmostonesideoftheconvexpolygon Hence Theconvexregionwillbeboundedbyatmostnedges 每個半平面最多形成相交區(qū)域的一條邊 因此相交區(qū)域不超過n條邊 6h planespentagon 9h planespentagon February10 2020 ZeyuanZhu 13 1 StatementoftheProblem Payattentionthatintersectionsometimesyieldsaline aray aline segment apointoranemptyregion 注意相交后的區(qū)域 有可能是一個直線 射線 線段或者點 當然也可能是空集 line ray line segment point emptyset February10 2020 ZeyuanZhu 14 2 ConvexPolygonIntersection CPI凸多邊形交預(yù)備知識 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 主要思想 以兩凸邊形邊的交點為分界點 將邊分為內(nèi) 外兩種 內(nèi)邊互相連接 成為所求多邊形 圖中粗線條 PolygonA PolygonB February10 2020 ZeyuanZhu 17 2 ConvexPolygonIntersection Supposethereisaverticalsweepline performingleft to rightsweep Atanytime thereareatmostfourintersectionsfromsweeplinetoeithergivenpolygon 假設(shè)有一個垂直的掃描線 從左向右掃描任何時刻 掃描線和兩個多邊形最多4個交點 PolygonA PolygonB Bu Au Bl Al Sweepline February10 2020 ZeyuanZhu 18 2 ConvexPolygonIntersection theloweronebetweenAuandBu andtheupperonebetweenAlandBl formanintervalofthecurrentinnerregion theredsegmentinbold Au Bu中靠下的 和Al Bl中靠上的 組成了當前多邊形的內(nèi)部區(qū)域 PolygonA PolygonB Bu Au Bl Al Sweepline February10 2020 ZeyuanZhu 19 2 ConvexPolygonIntersection Letuscallthex coordinatestobesweptx events Obviously thesweeplinemaynotgothroughallthex eventwithrationalcoordinates 我們稱被掃描線掃描到的x坐標叫做x事件 當然 我們不能掃描所有有理數(shù) 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 總時間復(fù)雜度可以用遞歸分析法 February10 2020 ZeyuanZhu 24 4 MyNewSolution Sort and IncrementalAlgorithm S I我自創(chuàng)的排序增量算法 February10 2020 ZeyuanZhu 25 4 Sort and IncrementalAlgorithm Definitionofh plane spolarangle forh planelikex y constant wedefineitspolarangleto 半平面的極角定義 比如x y 常數(shù)的半平面 定義它的極角為 February10 2020 ZeyuanZhu 26 4 Sort and IncrementalAlgorithm Step1 Separatetheh planesintotwosets Onehaspolaranglesof theotherhasthoseof Step1 將半平面分成兩部分 一部分極角范圍 另一部分范圍 February10 2020 ZeyuanZhu 27 4 Sort and IncrementalAlgorithm 考慮 的半平面 另一個集合類似地做Step3 4 將他們極角排序 對極角相同的半平面 根據(jù)常數(shù)項保留其中之一 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 我們要繼續(xù)交點檢查 如果還在右邊我們要繼續(xù)出棧 直到當前交點在棧頂交點的左邊 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 重復(fù)運作直到不再有更新出現(xiàn) 迭代 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算法的每一步都是線性的 通常我們用快速排序?qū)崿F(xiàn)Step2 總的時間復(fù)雜度為O nlogn 隱蔽其中的常數(shù)因子很小 February10 2020 ZeyuanZhu 41 5 ConclusionandPracticalUse總結(jié)和實際應(yīng)用 February10 2020 ZeyuanZhu 42 5 ConclusionandPracticalUse Greatideasneedlandinggearaswellaswings S IalgorithmseemstoworkinthesametimecomplexityasD Calgorithm butsomeoverwhelmingadvantagesofimplementingS Iholds Greatideasneedlandinggearaswellaswings S I算法似乎和D C算法時間復(fù)雜度相同 但是它有著壓倒性 overwhelming 的優(yōu)勢 February10 2020 ZeyuanZhu 43 5 ConclusionandPracticalUse ItismucheasiertocodeS IprogramthanD Cone TheprograminC programminglanguagetakeslessthan3KB 新的S I算法代碼容易編寫 相對于D C大大簡單化 C 程序語言實現(xiàn)S I算法僅需3KB不到 February10 2020 ZeyuanZhu 44 5 ConclusionandPracticalUse ThecoefficienthiddenunderS Ialgorithm scomplexityisextraordinarilysmallerthanD C sincewenolongerneedO nlogn numberofintersectioncalculates Ingeneralspeaking S IprogramrunsapproxfivetimesfasterthanD Cone S I算法復(fù)雜度中的系數(shù) 遠小于D C 因為我們不再需要O nlogn 次交點運算 通常意義上來講 S I程序比D C快五倍 February10 2020 ZeyuanZhu 45 5 ConclusionandPracticalUse Ifthegivenh planesareallin oranyspanof S Iprogramcanbesho