半平面交的新算法及其实用价值.docx

半平面交的新算法及其实用价值.docx

《半平面交的新算法及其实用价值.docx》由会员分享，可在线阅读，更多相关《半平面交的新算法及其实用价值.docx（10页珍藏版）》请在冰点文库上搜索。

半平面交的新算法及其实用价值

半平面交的新算法及其实用价值

Keywords:

Half-plane,Intersection,FeasibleRegion,Algorithm,Polygon,Practical

Abstract

主旨:

半平面的交是当今学术界热烈讨论的问题之一，本文将介绍一个全新的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;implementedpartlyinJune2005;problemsetinJuly2005;publicizedasapostinUSENET,November6,2005.

1.Introduction

Alineinplaneisusuallyrepresentedasax+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的半平面，找到所有满足它们的点所组成的点集

AsFigureiTwoexamplesofHPI.（b）givesanexampleofunboundedintersectionarea.describes,thefeasibleregion,whichistheintersection,formsashapeofconvexhullbutpossiblyunbounded.However,weshalladdfourh-planesformingarectangle,whichislargeenoughtomakesuretheareaafterintersectionsfinite.Inthefollowingsections,wesupposethefeasibleregionisboundedwithafinitearea.

合并后区域形如凸多边形，可能无界。

此时增加4个半平面保证面积有限

Eachh-planebuildsupatmostonesideoftheconvexpolygon,hence,theconvexregionwillbeboundedbyatmostnedges.Payattentiontheintersectionsometimesyieldsaline,aray,aline-segment,apointoranemptyregion.每个半平面最多形成相交区域的一条边，因此相交区域不超过n条边。

注意相交后的区域，有可能是一个直线、射线、线段或者点，当然也可能是空集。

2.ConvexPolygonIntersection（abbr.CPI）

IntersectingtwoconvexpolygonsAandBintoasingleone,canbeproperlysolvedviaLineSegmentIntersectioninO（nlogn）time,whenthereareO（n）edges.Wewillsketchoutaneasierandmoreefficientway,namedplanesweepmethod.

求两个凸多边形A和B的交（一个新凸多边形）。

我们描绘一个平面扫描法。

Themainideaistocalculateintersectionsofedgesascuttingpoints,andbreakboundariesofAandB,intoouteredgesandinneredges.Thesegmentsofinneredgesestablishtiestoeachother,andformtheshapeofapolygon,whichistheexpectedpolygonafterintersection.InFigureiiHowthesweeplineworks.“

”potentiallyshowsnextx-event.,inneredgesareindicatedbythicksegments,whichformaboldoutlineoftheintersection.主要思想:

以两凸边形边的交点为分界点，将边分为内、外两种。

内边互相连接，成为所求多边形。

Supposethereisaverticalsweepline,performingleft-to-rightsweep.Thex-coordinatestobesweptarecalledx-events.Atanytime,thereareatmostfourintersectionsfromsweeplinetoeithergivenpolygon:

假设有一个垂直的扫描线，从左向右扫描。

我们称被扫描线扫描到的x坐标叫做x事件。

任何时刻，扫描线和两个多边形最多4个交点

totheupperhullofA（namethatintersectionAuforshort）

tothelowerhullofA（namethatintersectionAlforshort）

totheupperhullofB（namethatintersectionBuforshort）

tothelowerhullofB（namethatintersectionBlforshort）

LookatFigureiiHowthesweeplineworks.“

”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）.

3.Commonsolution:

4.Divide-and-ConquerAlgorithm（abbr.D&Q）

Thebasicapproachissimple,dependsondivide-and-conqueridea.

Divide:

Partitionthenh-planesintotwosetsofsize

and

.

Conquer:

Computethefeasibleregion（intersection）recursivelyofbothtwosub-sets.

Combine:

Computetheintersectionoftwoconvexpolygons,bylinearCPIalgorithmdescribedin§2.

分:

将n个半平面分成两个n/2的集合.

治:

对两子集合递归求解半平面交.

合:

将前一步算出来的两个交（凸多边形）利用第2章的CPI求解.

Thetotaltimecomplexityofthesolutioncanbecalculatedviarecursiveequation:

总时间复杂度可以用递归分析法.

5.MyNewSolution:

6.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?

常数的半平面，定义它的极角为?

π.

Definitionofh-plane’sconstant:

fortheh-planelikeax+by≤c,wesayitsconstantisc.

MynewSort-and-IncrementalAlgorithmseemslengthysinceIamgoingtointroduceitindetails:

Step1:

将半平面分成两部分，一部分极角范围（-?

π,?

π]，另一部分范围（-π,-?

π]∪（?

π,π]

Step2:

考虑（-?

π,?

π]的半平面（另一个集合类似地做Step3/4），将他们极角排序。

对极角相同的半平面，根据常数项保留其中之一。

Step3:

从排序后极角最小两个半平面开始，求出它们的交点并且将他们押入栈。

每次按照极角从小到大顺序增加一个半平面，算出它与栈顶半平面的交点。

如果当前的交点在栈顶两个半平面交点的右边，出栈（pop）。

前问我们说到出栈，出栈只需要一次么？

Nie!

我们要继续交点检查，如果还在右边我们要继续出栈，直到当前交点在栈顶交点的左边。

Step4:

相邻半平面的交点组成半个凸多边形。

我们有两个点集，（-?

π,?

π]给出上半个，（-π,-?

π]∪（?

π,π]给出下半个

初始时候，四个指针p1,p2,p3andp4指向上/下凸壳的最左最右边。

p1,p3向右走，p2,p4向左走。

任意时刻，如果最左边的交点不满足p1/p3所在半平面的限制，我们相信这个交点需要删除。

p1或p3走向它右边的相邻边。

类似地我们处理最右边的交点。

重复运作直到不再有更新出现——迭代。

除了Step2中的排序以外，S&I算法的每一步都是线性的。

通常我们用快速排序实现Step2，总的时间复杂度为O（nlogn），隐蔽其中的常数因子很小

7.PracticalValueandLinearapproach

Greatideasneedlandinggearaswellaswings.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!

本算法瓶颈是排序，这里的排序不是比较排序，因此可以将快速排序替换成基数排序，降低程序渐进时间复杂度到线性。

Thesentimentofmycreation:

Aninventiondoesnotattributetosomeonewhocomesupwithideas.Mostpeoplehaveideas.Thedifferencebetweentheaveragepersonandtheinventoristhattheinventorforsomereasonbelievesonlyhimself,andhastheurgetoseehisideasthroughtofruition.HenriMatisse,aFrenchpainterandsculptor,eversaid‘thereisnothingmoredifficultforatrulycreativepainterthantopaintarose,becausebeforehecandoso,hehasfirsttoforgetalltherosesthatwereeverpainted.’Equippedwithbothidealisticandpracticalspiritofinnovation,Iamontheway.Howaboutyou?

Bibliography

1.KurtMehlhorn.DataStructuresandAlgorithmsVol3.Springer-Verlag,NewYork,1984.

2.ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein.Introductiontoalgorithms2ndEdition.MITPress,NewYork,2001

3.GillBarequet.ComputationalGeometryLecture4,Spring2004/2005.

4.KavithaTelikepalli.AlgorithmsandDataStructures,Lecture3,Winter2003/2004.