第六章 多面体面上任意两点间最短路径算法.pdf

第 卷 第 期 北 京 理 工 大 学 学 报 ! # 8-69! :-9# 年 月 !$$ # %’()’*+,-()-./0,1,(23()+,+4+0-.%0*5(-6-27 ;9!$$ 文章编号=$$?$@#A!$$B$#?$CC!?$ 多面体面上任意两点间最短路径算法 周培德 北京理工大学 信息科学技术学院计算机科学工程系 北京 A D $$$EB 摘 要 提出计算多面体面上任意两点之间最短路径的算法 近似算法 最短路径或近似最短路径算法 近似算法 = = F G 的思想是采用将折线不断嵌入三角形串上的方法 而另 个算法则是通过特定法线寻找三角形串 而且将这些三角 D ! D 形旋转到同一平面上 从而得到最短路径 前者的时间复杂性为 而后者的时间复杂性分别是 ! 及低于 D G ABD A B H I H I H I ! A! BG I 关键词 多面体面 最短路径算法 嵌入平面 三角形串 时间复杂性 = J J J J 中图分类号= C$L@ 文献标识码= %K ; MNOPQRSTUVWPQSTXYTPQSXVSZ[ST\XS]XX^_]P MQ‘RSQ[QaZPR^SVP^[ZPNaTXbQ[NYcQW[dX ? efgh K0,i0 A D D j0’+k0(+-.l-k4+0m*,0(*0’(in(2,(00,(2 m*5--6-.3(.-k’+,-(m*,0(*0’(i%0*5(i-27 /0,1,(23()+,+4+0-. D $$$ED B %0*5(-6-27 /0,1,(2 l5,(’ = M‘VSQ[dS %500’62-,+5k)’00)0(+0i.-*-k4+,(2+50)5-+0)+’+5o0+p00(+p-’o,+’7 = J -,(+)-(’-6750i’6)4.’*0 g(0,)’(’-q,k’+0’62-,+5k +50-+50+p-*’(-o+’,(+50 9 )5-+0)+’+5-’(’-q,k’+067)5-+0)+’+5 %50’-q,k’+0’62-,+5k ,)+-’i-+’k0+5-i D .-p5,*5+50o-r0(6,(0)’0*-()+’(+670ko0ii0i,(’)0,0)-.+,’(260) p500’)+50-+50