关闭

关闭

关闭

封号提示

内容

首页 【doc】求平面内两互不相交的凸多边形的内公切线的最优算法.doc

【doc】求平面内两互不相交的凸多边形的内公切线的最优算法.doc

【doc】求平面内两互不相交的凸多边形的内公切线的最优算法.d…

上传者: 背后动终成伤 2017-12-22 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《【doc】求平面内两互不相交的凸多边形的内公切线的最优算法doc》,可适用于综合领域,主题内容包含【doc】求平面内两互不相交的凸多边形的内公切线的最优算法求平面内两互不相交的凸多边形的内公切线的最优算法年月计算机第期求平面内两互不相交的凸多边形符等。

【doc】求平面内两互不相交的凸多边形的内公切线的最优算法求平面内两互不相交的凸多边形的内公切线的最优算法年月计算机第期求平面内两互不相交的凸多边形的内公切线的最优算法覃中平(华中理工大学数学系,武汉D)张焕国(武渡大学计算机科学系,武汉)ANOPTIMALALGORITHMTOFINDINTERNALLYCOMMONTANGENTSOFTWOCONVEXPOLYGONSQinZhongping(DeptolMashemzdc~Hzz~ongUni~er*ity口『ScienceadTechaJogyWahan)ZhangHuanguo(DeptofCompuwrSciecePuhaUiverHty,WuhaAbstract:LetPandQdenotetwoconvexpolygonsThecomputationalcomplexit,uffindingtheinternallycommontangentsofPandQisstudiedAnalgorithmisdescribedthatdeterminestheinternallyOOr~nlontangentsofPandQinO(ogmlogn)time,wheremanddenotethenumberofverticesofPandQ,respectivelyThisisoptimalintheworstcaseKeywords:Convexpolygon,internallyCOnlHlontangent,obliquesupportingline,algo~ithm,computationalgeometry顶点的凸多边摘要:设P与Q为平面内两个互不相交的分别具有,,l与个开j,它啦!的顶点嗣直角坐标描述并且沿其边界按顺时针方向依次列出本文给出求P与Q的内会切线(或称斜支撑线)的时问复杂度为(og蝌log)的最优算法,从而突破了李辉关于解决同一问题的时问复杂度为o(m#)的算法是最优的论断关键词:凸多边形,内公切线,斜支撑线,算法,计算几何一,主要定理求平面内两互不相交的凸多边形的内公切线(或称斜支撑线)的问题是计算几何中的率文年月日收到一中平,讲师,主要研究纠错编码,算法,密码学与计算机安全张焕胃,胃教授,中国密码学会理事,主要研究纠错编码,容锴计算,图形学,密码学与计算机安全计算机一个基本问题由于该问题在计算机图形学,VLSI设计及机器人学中的重要应用,目前已受到广泛的注意设P与Q为平面内两个互不相交的分别具有与一个顶点的凸多边形,在每一凸多边形以标准形式给定,即其顶点用直角坐标描述且沿其边界按颐时针方向依次列出的条件下李辉给出了求P与Q的内公切线的时间复杂度为()的算法,并证明了他的这一算法在时间复杂度上是最优的但因李辉的证明中有疏漏,故他的算法是最优算法这一结论还不能被肯定本文将KMehlhorn的求两凸多边形盼外公切线的方法改进后应用到求两凸多边形的内公切线的问题中来,得到下面昨定理设P与Q为平面内两个互不相交的分别具有m与个顶点的凸多边形,它们以标准形式给定,则可构造一个求P与Q的内公切线的时间复杂度为(ogmqlog)的算法并且这一算法的时间复杂度是最优的这一结果说明李辉关于他的算法在时间复杂度上是最优的结论不能成立同时从本文所给方法出发,可容易地构造一个求以标准形式表出的两凸多边形的外公切线的最优算法,由于这一最优算法不像KMehlhorn算法那样要求两凸多边形的顶点满足上的字典序(exlcographicordering),因而本文所得结果也是对KMehlhprn求两凸多边形的外公切线算法的改进与推广二,定理的证明符号,术语与约定大写英文字母P,Q表凸多边形,P,P"等表凸多边形P的顶点子序列,小写英文聿母p,等表凸多边形P的顶点,但字母表平面内的直线Pq:表过点P与g的直线一Pq:表过点p与g且有着从P到g的方向的有向直线Pq:从P点出发过g点的射线凸多边形P的距直线t最远的顶点p(f):凸多边形P的距直线最近的顶点suco(p):凸多边形P的给定顶点子序列中顶点P的后继顶点pre(p):凸多边形P的给定顶点子序列中顶点P的前序顶点【,P":凸多边形P的边界上从顶点P起顺时针至顶点P"所经过的P之顶点(含p'与P")所构成的P的顶点子序列从P到Q的左(右)内公切线:若直线Pq为P与Q的内公切线且P在有向直线另的左(右)侧,则有向直线Pq称为从P到Q的左(右)内公切线或左(右)斜支撑线触点:直线Pq过凸多边形P的顶点P且凸多边形P位于直线Pq的一侧,则称点p,为直线加关于P的触点,如图l(a)所示进点:有向直线加与凸多边形P相交且由顶点P进入凸多边形P,则称点P为有向直线pg关于P的进点,如图l(b)所示覃中平等:求平面内两互不相交的凸多边形的内公切线的最优算法出点:有向直线与凸多边形P相交且从顶点p离开凸多边形P,则称点p为有向宣线关于P的出点,如图()所示)fbJf图l下面我们约定P与Q为平面内两个互不相交的分别具有m与个顶点的凸多边形并且它们都以标准形式给定王几个引理引理I(初始化过程)可在(ogmlog)时间内求得P与Q的顶点子序列P与Q使得P与Q含有从P到Q的左内公切线的切点而不含有从P到Q的右内公切线I的切点证明由【】给出的算法,可在(ogLlog时间内求得直线,使得凸多边形P与Q分居直线f的两旁下面不失一般性假定P,Q与直线的位置关系如图所示卣】之算法l可在(ogmlg)时间内求得P与Q的个顶点:l(J),p【f),…【f与口cJ由图所示P的顶点子序列P一pcJ,,,】与Q的顶点子序列Q一gm),口一(f)】含有从P到Q的左内公切线的切点而不合有右内公切线的切点引理证毕图引理z(折半过程)存在着确定的规则,按该规则可由引理l给出的顶点子序列P,与Q出发生成凸多边形P与Q的顶点子序列串P,,P",…,P"()与Q,Q,Q,…,P''()使得(i)由生成P'及由Q生成Q所需时间均为有限步(fl,…一,f一,,…,一),(ii)P"由P截去一半而得,Q'田Q截去一半而得,r…,一计算|}Ii报,,一,,…,一),一(iii)P【)一{,Q一{g且有向直线p为从P到Q的左内公切线证明设我们已生成子序列串P,,…,P"与Q,Q",…,Q'f),这里)一【,】,Q一,g,"令P为【p','的中点,g为【,"】的中点一在判别点P为有向直线阳对于凸多边形P的进,触,出点情形及g点为有向直线pg对于凸多边形Q的进,触,出点情形后,报据表所列规则,要么可由P【"生成P",要么可由QU)生成Q(H"且两者至少有一个成立重复上述过程便可得顶点序列串()与()当序列串()与()中的某一串首先生成倪台一个或二个顶点的序列时,如何继续进行上述折半生成过程,详见附录A由P"'生成…'及由Q生成Q『都只需判别P点与g点为进点或触点或出点这样的属性,而这种判别仅需对有限个角度进行计算,因而引理的条件(i)成立再由表t给出的折半生成方法又知条件(h)也成立引理条件(iii)的成立基于下述断言:对f一,,…,及,一,,一,,u与Q(都台有从P到Q的左内公切线的切点现甩归纳法证明这一断言设P【,Qu)含有从P到Q的左内公切线的切点,因P""与Q'"是由pet)与Qu)分种不同情形按表所列规则生成,故下面也分种情况论证P【"与Q叶"仍含有从P到Q的左内公切线的切点:情形l:自明情形,,,:分别参见图之(a),(b),(c)与(d)所示,容易知道各图的画着波浪线的部分不含有从P到Q的左内公切线的切点,故表所列相应规则正确表由P与Q'"生成'或Q'川'的规剐序号点唇性日点属性睁列P''的起止点序刊Q',''的起止点触点触点p即为切点口即为切点触点进点P,加,"触点出点P,加',出点触点,",出点出点,f'出点进点觅注见注进点触点,p,们进点进点,P连点出点'P,袁往:若射线与射线:丽相交或平行,则p(i十】】=succ(),若射线I与射线:相交或平行,则QI害suet(),,情形,,:它们分别与情形,,对称情形:如图所示,射线与射线位于直线加的两侧,昂期覃中平等:求平面内两互不相交的凸多边形的内公切线的最优算法'c)(d】图而两者不会相交,这样要么是射线与射线相交或平行,要么是射线gsucc(g)与射线SHCC)p相交或平行现在我们对表l情形所列折半规则的前半部分"若射线psucc(s,)与射线succ(q)q相交或平行,则"一succ),给以证明如图所示,射线psucc(与射线succ(相交,此时点P不是从P到Q的左内公切线的切点,原因如下,假若P为切点,则左内公切线与Q相切的切点应位于图阴影所示区域内,但由于Q在有向直线图qsuc~(q)的右侧,因而Q上任一点又绝不会在阴影所示区域内,此矛盾说明p点不是协点,同理pre(,pre(pre(p)),…,P诸点都不是从P到Q的左内公切线的切点,于是欲证明的规则成立至此种情况讨论毕即我们用归纳法证明了引理条件(iii)成立引理证毕引理(下界)求凸多边形P与Q的左内公切线的算法的时间下界为口(og(max{m,))),这里算法以涉及至多H(H为一常数)个点的坐标的有限步算术运算与比较为基础证明令矗lmax{m,^我们以A表示整个求凸多边形P与Q的左内公切线的问题类,以B表示求三角形P与凸‰边形Q的左内公切线的问题类,而以c表示求过点P且与凸边形Q相切的直线的问题类显然阃题类A,B,c有着顺序包含关系,故若以A(max{m,))表示求解问题类A的算法的时间下界,则对充分大的m与有:A(max{,))B(max{,‰)c(max{I,‰))下面我们通过证明求解问题类c,即求过点P且与凸边形Q相切的直线的算法的时间下界c(max{I,))一口(og‰)来完成本引计算机理的证明由于凸边形Q以沿边界的顶点序列这一方式给定,Q的任一顶点都有可能是过凸多边形Q外的一点且与Q相切的直线切于Q的切点(园点p与凸多边形Q的随意性使然),故以涉及至多H(H为常数)个点的坐标的有限步算术运算,与比较为基本操作的任一算法在一次基本操作之后,只能给出欲求切点在给定的Q之顶点序列中相对于基本操作所涉及的Q的某顶点(以下称为该基本操作的特定点)的相对次序,这样类似于SBaase对于颠序查找问题的处理,可用判定尉(decisiontre~)来模拟求过点p且与凸迪形Q相切的直线的算法,这里判定树为有个结点的二元树,每一结点代表Q的一顶点,树的根为算法第二次基本操作的特定点,而由根出发的二支子树由基本操作给定,如此递归直至树的叶子显然在最坏情况下该算法所用时间正比于该判定树的从根到叶的最长通路的路长,这样求解问题类C的算法的时间下界(在最坏情况下)为口(g)B【理证毕注:求解引理中问题类C的算法的时间下界的估计也可以【的方法处理定理的证明证明由引理与可构造出一个时间复杂度为(togmtog)的求凸多边形P与Q的两条内公切线的算法,再由引理知,求P与Q的内公切线的算法的时间下界为口(og(max{m,}))由于(ogmlog)一日(og(max{m,))),因而所给算法在时间上是最优的,这里(,()),口(,(一)),(,())的意义同【lO】定理证毕三,结束语对于求平面内两互不相交的凸多边形的内公切线问题,本文估计了这一问题的时间下界,构造了一个解决这一问题的最优算法对于求平面内两凸多边形的外公切线问题,我们可建立与本文引理l,,相类似的结果,从而可构造出一个求两凸多边形的外公切线的最优算法由于这一最优算法不要求两凸多边形的顶点满足中的字典序,因而这一最优算法比KMehlhorn的算法更为实用本文的求两凸多边形的内公切线算法已在IBMPCiXT机上用TURBOPASCAL语言实现车文工作得到陶仁骥研究员的支持,在程序设计方面王,』,芹,昊建红两同志给以帮助,在此一井致'坩附录A引理证明中根据表所列规则用折半方法生成顶点序列串()与()时,若串()P,P,…,P)一{p)首先全部生成,而串()已生成的为QQ…,Q罩中平等:求平面内两互不相交的凸多边形的内公切线的最优算法这里Q卿所含顶点多于两个,则此时可直接令序列P"的中点为,取Q"的中点g后,仍可由表所列规则逐步生成Q"",Q"),一,Q一{g),原因如下:由于为一从P到Q的左内公切线切p的切点,故只能为有向直线,关于P的触点或出点,这样只能有表所列情形l,,…,发生,且当情形发生时射线qsucc(q)与射线succ(p)P必相交,因此可根据袁所列相应规则由Q"生成"又若串()在生成过程中已生成有P,P",…,Pl,这里只含两顶点,即P"一{,),此时可取P【I的中点为线段的几何中点,然后仍按表l所列规则继续进行折半生成串()与()的过程由于为凸多边形P的虚拟的顶点,因此其在P"被折半后就可删除掉这样串()与()总可按表l所列规则折半地生成考文献】GTT口jmComputationalGeometry(EdGTTou~saim),North=HMlandsfIJHHoporoft,DAJo*ephandWhkesides,ProordFOCS,O一fJRelfandMshfirProcthFOCS,,一{【TLzanoP~rezandMAWesley,AnAlgnrithmforPlanningColli$on=FreePathsAmongPo!edraIObstaclesCommACM,o()f李辉,凸多迪形可移动性的最优判定算法,中国科学(^辑),l(),Iir】KMehLhora,DataStructures加dAlgorithms:Multiddmensloa~lSearehin$们dCompmztion~lGeomerrySpringerVerlag,Berlin,,一【HEddsbrumlcr,CompatiagtheExtremeDi~tancebetweenTwoConvelPMygnnJAorlthms,'f),l{{CSBaas~,COmputerAtgoritbmsIotroductioatoDesign如dAoais,AddisonWesley,Lond卢开醴,组合数学,算法与丹析(下册),捐华大学出皈社,北京,IAGottliehandCPKrushaComplexityResultsforPermutingDataandOtherComphtadon曲P且rlProcessorsJcM:(),i,

职业精品

用户评论

0/200
    暂无评论

精彩专题

上传我的资料

热门资料

资料评价:

/12
0下载券 下载 加入VIP, 送下载券

意见
反馈

返回
顶部