歡迎閱讀本文檔，希望本文檔能對您有所幫助!歡迎閱讀本文檔，希望本文檔能對您有所幫助!感謝閱讀本文檔，希望本文檔能對您有所幫助!感謝閱讀本文檔，希望本文檔能對您有所幫助!歡迎閱讀本文檔，希望本文檔能對您有所幫助!感謝閱讀本文檔，希望本文檔能對您有所幫助!半平面交的新算法及其實用價值Keywords:Half-plane,Intersection,FeasibleRegion,Algorithm,Polygon,PracticalAbstract主旨:半平面的交是當今學術界熱烈討論的問題之一，本文將介紹一個全新的O(nlogn)半平面交算法，強調它在實際運用中的價值，并且在某種程度上將復雜度下降至O(n)線性。最重要的是，我將介紹的算法非常便于實現.§1introduceswhathalf-planeintersectionis.§2preparesalinearalgorithmforconvexpolygonintersection(abbr.CPI).Equippedwithsuchknowledge,acommonsolutionforHPIisbrieflydiscussedin§3.Then,mynewalgorithmemergesin§4detailedly.Notonlyasaconclusionofthewholepaper,§5alsodiscussitsfurtherusagepracticallyandcomparesitwiththeolderalgorithmdescribedin§3.§1什么是半平面交.§2凸多邊形交預備知識.§3簡要介紹舊D&C算法.§4揭開我的新算法S&I神秘面紗.§5總結和實際運用.Timestamps:CameupwithitinApril2005;implementedpartlyinJune2005Thesub-problemofHPIappearedinUSAInvitationalComputingOlympiadcontest.;problemsetinJuly2005SetanHPIprobleminPekingUniversityOnlineJudge,withbriefintroductionaboutthealgorithm.;publicizedasapostinUSENET,November6,2005Thesub-problemofHPIappearedinUSAInvitationalComputingOlympiadcontest.SetanHPIprobleminPekingUniversityOnlineJudge,withbriefintroductionaboutthealgorithm.URL:/group/sci.math/msg/68e9d9fc634f0d92IntroductionAlineinplaneisusuallyrepresentedasax+by=c.Similarly,itsinequalityformax+by≤crepresentsahalf-plane(alsonamedh-planeforshort)asonesideofthisline.Noticethatax+by≤cand-ax-by≤-cshowoppositeh-planesunlikeax+by=cand-ax-by=-c.Half-PlaneIntersection(abbr.HPI)considersthefollowingproblem:眾所周知，直線常用ax+by=c表示，類似地半平面以ax+by≤(≥)c為定義。Givennhalf-planes,aix+biy≤ci(1≤i≤n),youaretodeterminethesetofallpointsthatsatisfyingalltheninequations.給定n個形如aix+biy≤ci的半平面，找到所有滿足它們的點所組成的點集AsREF_Ref122367617Figurei TwoexamplesofHPI.(b)givesanexampleofunboundedintersectionarea.describes,thefeasibleregion,whichistheintersection,formsashapeofconvexhullbutpossiblyunbounded.However,weshalladdfourh-planesformingarectangle,whichislargeenoughtomakesuretheareaafterintersectionsfinite.Inthefollowingsections,wesupposethefeasibleregionisboundedwithafinitearea.合并后區域形如凸多邊形，可能無界。此時增加4個半平面保證面積有限LINKWord.Document.8"LINKWord.Document.8"文檔2""OLE_LINK3"\a\r??!??????????.(a)(b)Eachh-planebuildsupatmostonesideoftheconvexpolygon,hence,theconvexregionwillbeboundedbyatmostnedges.Payattentiontheintersectionsometimesyieldsaline,aray,aline-segment,apointoranemptyregion.每個半平面最多形成相交區域的一條邊，因此相交區域不超過n條邊。注意相交后的區域，有可能是一個直線、射線、線段或者點，當然也可能是空集。ConvexPolygonIntersection(abbr.CPI)IntersectingtwoconvexpolygonsAandBintoasingleone,canbeproperlysolvedviaLineSegmentIntersectioninO(nlogn)time,whenthereareO(n)edges.Wewillsketchoutaneasierandmoreefficientway,namedplanesweepmethod.求兩個凸多邊形A和B的交（一個新凸多邊形）。我們描繪一個平面掃描法。Themainideaistocalculateintersectionsofedgesascuttingpoints,andbreakboundariesofAandB,intoouteredgesandinneredges.Thesegmentsofinneredgesestablishtiestoeachother,andformtheshapeofapolygon,whichistheexpectedpolygonafterintersection.InREF_Ref122369694\hFigureii Howthesweeplineworks.“”potentiallyshowsnextx-event.,inneredgesareindicatedbythicksegments,whichformaboldoutlineoftheintersection.主要思想:以兩凸邊形邊的交點為分界點，將邊分為內、外兩種。內邊互相連接，成為所求多邊形。Supposethereisaverticalsweepline,performingleft-to-rightsweep.Thex-coordinatestobesweptarecalledx-events.Atanytime,thereareatmostfourintersectionsfromsweeplinetoeithergivenpolygonAssumethereisnoedgeinpolygonsparalleltothesweepline.Assumethereisnoedgeinpolygonsparalleltothesweepline.Ifsuchsituationhappens,wecouldrotatetheplaneinproperangle,orelse,weneedgoodsensetojudgeagreatmanyspecialcases.假設有一個垂直的掃描線，從左向右掃描。我們稱被掃描線掃描到的x坐標叫做x事件。任何時刻，掃描線和兩個多邊形最多4個交點totheupperhullofA(namethatintersectionAuforshort)tothelowerhullofA(namethatintersectionAlforshort)totheupperhullofB(namethatintersectionBuforshort)tothelowerhullofB(namethatintersectionBlforshort)BuBuAuBlAlSweeplinePolygonAPolygonBLINKWord.Document.8"文檔2""OLE_LINK4"\a\r??!??????????.LookatREF_Ref122369694Figureii Howthesweeplineworks.“”potentiallyshowsnextx-event.,theloweronebetweenintersectionsAuandBu,andtheupperonebetweenintersectionsAlandBl,formanintervalofthecurrentinnerregion–theredsegmentinbold.Au、Bu中靠下的，和Al、Bl中靠上的，組成了當前多邊形的內部區域。Obviously,thesweeplinemaynotgothroughallthex-eventwithrationalcoordinates.CalltheedgeswhereAu,Al,BuandBlare:e1,e2,e3ande4respectively.Thenextx-eventshouldbechosenamongfourendpointsofe1,e2,e3ande4,andfourpotentialintersections:e1∩e3,e1∩e4,e2∩e3ande2∩e4.當然，我們不能掃描所有有理數！稱Au,Al,Bu,Bl所在的邊叫做e1,e2,e3,e4，下一個x事件將在這四條邊的端點，以及兩兩交點中選出。TheaboveoperationcouldbeimplementedwithO(n)runningtime,sincethereareO(n)x-events,andthemaintenanceofAu,Al,BuandBltakesonlyO(1).Commonsolution:

Divide-and-ConquerAlgorithm(abbr.D&Q)Thebasicapproachissimple,dependsondivide-and-conqueridea.Divide:Partitionthenh-planesintotwosetsofsizeand.Conquer:Computethefeasibleregion(intersection)recursivelyofbothtwosub-sets.Combine:Computetheintersectionoftwoconvexpolygons,bylinearCPIalgorithmdescribedin§2.分:將n個半平面分成兩個n/2的集合.治:對兩子集合遞歸求解半平面交.合:將前一步算出來的兩個交(凸多邊形)利用第2章的CPI求解.Thetotaltimecomplexityofthesolutioncanbecalculatedviarecursiveequation:總時間復雜度可以用遞歸分析法.MyNewSolution:

Sort-and-IncrementalAlgorithm(abbr.S&I)Definitionofh-plane’spolarangle:fortheh-planelikex-y≥constant,wedefineitspolarangleto?π.fortheh-planelikex+y≤constant,wedefineitspolarangleto?π.fortheh-planelikex+y≥constant,wedefineitspolarangleto-?π.fortheh-planelikex-y≤constant,wedefineitspolarangleto-?π.半平面的極角定義:比如x-y常數的半平面，定義它的極角為?π.?π?π-?πLINKWord.Document.8"文檔1""OLE_LINK1"\a\r??!??????????.Definitionofh-plane’sconstant:fortheh-planelikeax+by≤c,wesayitsconstantisc.MynewSort-and-IncrementalAlgorithmseemslengthysinceIamgoingtointroduceitindetails:Step1:將半平面分成兩部分，一部分極角范圍(-?π,?π]，另一部分范圍(-π,-?π]∪(?π,π]LINKWord.Document.8"文檔1""OLE_LINK2"\a\r??!??????????.Step2:考慮(-?π,?π]的半平面(另一個集合類似地做Step3/4)，將他們極角排序。對極角相同的半平面，根據常數項保留其中之一。LINKWord.Document.8"文檔1""OLE_LINK1"\a\r??!??????????.LINKWord.Document.8"文檔1""OLE_LINK1"\a\r??!??????????.LINKWord.Document.8"文檔1""OLE_LINK2"\a\r??!??????????.LINKWord.Document.8"文檔1""OLE_LINK3"\a\r??!??????????.LINKWord.Document.8"文檔1""OLE_LINK4"\a\r??!??????????.LINKWord.Document.8"文檔1""OLE_LINK5"\a\r??!??????????.LINKWord.Document.8"文檔1""OLE_LINK6"\a\r??!??????????.Step3:從排序后極角最小兩個半平面開始，求出它們的交點并且將他們押入棧。每次按照極角從小到大順序增加一個半平面，算出它與棧頂半平面的交點。如果當前的交點在棧頂兩個半平面交點的右邊，出棧（pop）。前問我們說到出棧，出棧只需要一次么？Nie!我們要繼續交點檢查，如果還在右邊我們要繼續出棧，直到當前交點在棧頂交點的左邊。Step4:相鄰半平面的交點組成半個凸多邊形。我們有兩個點集，(-?π,?π]給出上半個，(-π,-?π]∪(?π,π]給出下半個初始時候，四個指針p1,p2,p3andp4指向上/下凸殼的最左最右邊。p1,p3向右走，p2,p4向左走。任意時刻，如果最左邊的交點不滿足p1/p3所在半平面的限制，我們相信這個交點需要刪除。p1或p3走向它右邊的相鄰邊。類似地我們處理最右邊的交點。重復運作直到不再有更新出現——迭代。upperupperhulllowerhullp3p4p1p2LINKWord.Document.8"文檔1""OLE_LINK2"\a\r??!??????????.(a)p3p4p1p2(b)p3p4p2(c)p1p3p4p2(d)p1p3p4p2(e)p1p3p4p2(f)p1*LINKWord.Document.8"LINKWord.Document.8"文檔1""OLE_LINK3"\a\r??!??????????.nointersectionforlowerhull除了Step2中的排序以外，S&I算法的每一步都是線性的。通常我們用快速排序實現Step2，總的時間復雜度為O(nlogn)，隱蔽其中的常數因子很小PracticalValueandLinearapproachGreatideasneedlandinggearaswellaswings.S&I算法似乎和D&C算法時間復雜度相同，但是它有著壓倒性(overwhelming)的優勢。新的S&I算法代碼容易編寫，相對于D&C大大簡單化，C++程序語言實現S&I算法僅需3KB不到.S&I算法復雜度中的系數，遠小于D&C，因為我們不再需要O(nlogn)次交點運算.通常意義上來講，S&I程序比D&C快五倍。Remark:intersectioncalculationsplaythemostimportantroleinbothalgorithmsduetoitsoperationalspeed(soslow,equivalenttohundredsofadditionoperations).CPI,thepreparativealgorithmwhichwillbecalledseveraltimesfromD&C,requiresO(n)numberofcalculations,whereforeitrisesthetotalrunningtimeup.Besides,S&IcalculatesO(n)timesinanycase.如果給定半平面均在(-?π,?π]（或任意一個跨度為π的區間），S&I算法可被顯著縮短，C++程序只需要約二十行。USAICO比賽中就出現了這樣一題。AsymptoticalOptimizationtolinear:Thebottleneckofthisalgorithmissorting.PayattentionthesortingisNOTacomparisonsort(sortingbasedoncomparison)!Thekeywordsforelementstobesortedarepolarangles,whichcanbecertainlydeterminedbygradient–adecimalfraction.Sincethen,wecanreplacetheO(nlogn)quick-sorttoO(n)radix-sort.TheasymptoticalcomplexityofalgorithmcandecreasetoO(n).AnywayO(n)approachusuallyrunsslowerthannlognonesforitsadditionalmemoryusage!本算法瓶頸是排序，這里的排序不是比較排序，因此可