ѧ
JOURNAL OF SOFTWARE
1999 10 7ڡNo.7 Vol.10 1999



άռе·
ʩ
ժҪڰһ໥͹άռΪѰ·NP.͹ĸkʱ,Ϊָʱ临Ӷ;k=1ʱ,ΪO(n2)nΪ͹Ķ.Ҫоk=2µ·,һO(n2)ʱڽ㷨.ýڴΪֹõĽO(n3logn).,˽Ӧõk>2κ,õĽΪO(x12i-1n2i).
ؼʡ·,͹,㼸,,Voronoiͼ.
ͼšTP301
The Problem of Shortest Path in 3D Space
SHI Hai-hu
(Hisense Technique Research CenterQingdao266071)
(Department of Computer Science and Technology Beijing University Beijing 100871)
Abstract The problem of computing the euclidean shortest path between two points in the three dimensional space bounded by a collection of convex disjoint polyhedral obstacles is known to be NP-hard and in exponential time for arbitrarily many obstacles. It can be solved in O(n2) time for single convex polyhedron obstacle (here n is the total number of vertices of polyhedron). In this paper, the author mainly researchs the shortest problem of the case of two convex polyhedral obstacles, and presents an algorithm that solves this problem in O(n2) time, and improves improving significantly previous best result O(n3logn) for this special case. On the other hand, the author also presents a better result O(x12i-1n2i) for the problem of shortest path amidst a fixed number of convex polyhedral obstacles.
Key wordsShortest path, convex polyhedron, computing geometry, geodesics, Voronoi graph.
,·Ϊ˶滮Ļ֮һ.ڻˡҰ⺽СҵԶͼԽԽܵǵĹע.ͨ,ڰһ֪ϰĻΪһϵͳѰűܰ·൱ѵ.,ϰ￴͹塢ϵͳƶʱ,·ͱɿɽ.
ڶάռе·,ÿͼİ취O(n2)ʱڼ·1ݣάռ,ʮ.ڰһ໥͹άռΪѰ·ǸNP2.kʱ,ָʱ临ӶõĽ3ݣk̶ʱ,ͼ.ף4ݶk=1ʱо,O(n3logn)㷨.,ף5ݸĽO(n2)k=2k>2,ĿǰõĽΪO(n3logn)6ݺO(n4k)7.
ڱ,ǽף1ݵļƹ㵽k=2,һO(n2)ʱڽ㷨.ĵ1ڼҪk=1µ·,2صk=2µĹ,Ҫk>2.
1͹ϵ·
Pһ͹,SPı,nΪPĶ,nʾPĸӶ.͹ϵ·,ʼXS,YS,ҪSXY·.
Ϊ˴ⷽ,ҪSʷ,õһµ͹P,ʹXҲΪPĶ,̵ʱ临ӶΪO(nlogn)8.,PĸӶȲ,PĶΪO(n).
ʹ¶.
(1) YSΪridge(ڸʼX),SٴXY·.RʾSridgeļ.
(2) YS-R,(X,Y)(Ϊ(Y))ʾXYΨһ·.
(3) Ц=(1,...,m)ʾ(Y)SıɵıУf=(f0,...,fm)ʾ(Y)Sɵ,Цifi-1fi,i=1,...,mXf0,Yfm(ͼ1ʾ).

ͼ1͹·ıߡ
(4) Yıк,Խf0,...,fmչͬһƽL.ͨһѭ.Ƚf0L,ʹXʼλһ£Ѿf0,...,fi-1չ,ҶL,ôŦifiչ,ʹ֮fi-1ͬ,ʱ,fiҲL,Ҵڦiһ.ǳLΪεչƽ,X,Y,,f LеӳΪX,Y,Ρ,f䣨ͼ2ʾ.

ͼ2εչƽ漰Ӱӵ˵
(5) Ӱshadow(X,Ρi,Ρi+1),L,ΡiXΪԴڦΡi+1ϵӰӣͼ2ʾ. 
i=0ʱ,shadow(X,,Ρ1)={YYʦΡ1},Цʾռϣ
0<i<mʱ,shadow(X,Ρi,Ρi+1)={YYʦΡi+1,ֱ߶XYΡ1,...,Ρiཻ}.
ǽshadow(X,Ρi,Ρi+1)Sϵӳshadow(X,Ρi,Ρi+1)ΪΡiXΪԴڦΡi+1ϵӰ.
(6) Ӱshadow(X,Ρi,fi),L,ΡiXΪԴfiϵӰӣμͼ2.
i=0ʱ,shadow(X,,f0)={YYf0},Цʾռϣ
0<i<mʱ,shadow(X,Ρi,fi)={YYfi,YΡi,ֱ߶XYΡ1,...,Ρiཻ}.
ǽshadow(X,Ρi,fi)Sϵӳshadow(X,i,fi)ΪiXΪԴfiϵӰ.ע, shadow(X,i,i+1)=shadow(X,i,fi)ɦi+1,ӰӿΪ.
г͹·ԣ4ݣ
(1) ·ͨPĶ㣨ʼյΪ⣩
(2) ·Pÿߣÿ棩Ľ㣨ߣ಻11
(3) ·ཻ
(4) κͬʼ·,Ҫôཻ,Ҫôеĳһ·
(5) ͹֮һڲ,֮·ǲߣ
(6) ཻ,ô˲ڦεչƽһֱ߶.
㦰(Y)ɷֽ,,ȼ·⣺
(1) (Y)ıЦΣ
(2) 㦰(Y)иߵĽ.
ݲߵչ,2׽.1һ㷽ǣX,ϣPԤ,ĿY,ܹټXY·.ͨ,ԤҪʱ·ʱ临Ӷ.ף1(sequence tree)ķҦε,һһֲ桱㷨,ø㷨ɵĲΪn,ÿһĿΪO(n).㷨Ҫ˼·ǣ͹PS,SϵʼX,SXYS·.,X,ĸΪX,ǸΪͬ·еĵ㼯,ҳYӦĽ,ɴӸýб߹ɵмΪXY·ıУ,ݲ,·ñиߵĽ.
2͹·
໥յ͹P1,P2,ǵıͶֱΪS1,S2n1,n2XS1,YS2,ҪS1S2XY·(Y).Ը.
͹·ԣ5,6ݣ
(1) ·3ӶΣS1Xɵ㡱tS1·t㡱lS2ֱ߶ԼS2lY·(ͼ3ʾ).

ͼ3͹·
(2) Xlӣ,ǵP1,P2ڲκν㣩,t=XtY,l=Yt=Xl=Y,tlڶӦı.
(3) ·ᾭS1,S2ϵκζ㣨X,YǶ嶥XY⣩.
·3·,2Ϊֱ߶Σ13ڵ͹,ʹף5ݵ㷨.,͹·ɹΪɵ.·ıΪ=(1,...,m1+m2),Ц1,...,m1S1,m1+1,...,m1+m2S2,tʦm1,lʦm1+1,·ֿɷΪ⣺
(1) ɵtlڵıߦm1,m1+1
(2) ɵtl.
ף6й߿ӵĶɵã
(1) XS1ߦiS2,ô,iɷֳ,ʹеĳX,һXӣ
(2) ߦ1S12S2,ô,1ɷֳ3,ʹеĳ2,2.ڦ2Ȼ.
Ϊ˱,ǽƽΪf(l),lΪƽıߣƽf(l)ĲΪf*(l),Ҳһƽ,f(l)λͬһƽ,ͬ,෴ΪfABC(BC)Ϊf(BC).
ƽаƽ·⣺ƽf(l1)f(l2)໥ƽ,һཻ,Xf(l1),Yf(l2),ҪXYξl1l2·.ΪXl1ƽͬԼl1l2ƽ3µ·,ԺмٶX,Yڰƽı,ƽ治ͬ,ǵı߲ƽ.
ΪԤ֪ʶ,ȸ.
1. ƽLԼֱl1,l2,㣺
(1) l1L
(2) l2L,LƽУ
(3) l1l2Ȳƽ,ֱֲ.
ô,Xl2l1ΪתLཻڵX1X2,Xl2еʱ,ӦX1,X2ɵĹ켣Ϊ˫.
֤.
˫߾ʣ
2. WΪ˫x2/a2-y2/b2=1(x>0)x<0,xཫWָ5,֮3߶.
֤.
ں,ٶֻ֮1߶,Xÿֻ˫ཻһ.ڰ3߶ε,ֻҪĹظ3μ.
ݶ1Ͷ2ɵã
3. ƽаƽ·,XY·l1,l2ĽΪA,B,l1Ϊ,l2ת켣f*(l1)ĽΪW2l2Ϊ,l1ת켣f*(l2)ĽΪW1Al2תW1ཻA䣻Bl1תW2ཻB,ڰf(l1)ƽL1,X,A,B㹲ߣڰf(l2)ƽL2,A,B,Y㹲(ͼ4ʾ).

ͼ4㹲߶
֤ݵ͹·ԣ6֤.
ݶ3ɵã
4. ƽаƽ·,Y1,Y2f(l2)(Y1Y2),XY1(Y2)·l1,l2ĽֱΪA1,B1(A2,B2)l1Ϊ,l2ת켣f*(l1)ĽΪW2l2Ϊ,l1ת켣f*(l2)ĽΪW1A1,A2l2תW1ཻA1,A2B1,B2l1תW2ཻB1,B2f(l1)L1,f(l2)L2ͼ5aʾ,L2,A1Y1A2Y2ཻ.

ͼ5ཻ
֤l1l2Ĺll2ཻO,OƽL2l1ƽl1ԹlΪY,l1ΪZ,Oֱl1,l1ֱΪXὨֱϵl1l2ļнΪ,X,W2ֱͶӰL2,õͼ5(b)ʾͶӰͼ.,ƽ棨X-Zϵ,l1,l2,W1,W2ķ̷ֱΪ
l1:x=0,
l2:x=tg.z,
W1:(tg2-1)*x2+2tg*xz+a2=0(x<0),
W2:x=(a2+tg2*z2)1/2,
aΪֱl1,l2ľ.Ȼ,W1(W2)ϵĵl2(l1)ϵĵһһӦ.
A1,A2,B1,B2,A1,A2,B1,B2ֱΪ
(z1,x1),(z2,x2),(z3,x3),(z4,x4),(z5,x5),(z6,x6),(z7,x7),(z8,x8).
ǰļ,XÿֻW2ཻ1,ôA1B1һһӦ,A1B1һһӦ.ͬɵA2B2һһӦ.,z1<z2,ôɵz3<z4,z5<z6,z7<z8.
(1) A1B1A2B2ཻ,A1B1A2B2ཻ,A1B1,A2B2ǴXϵ߶ì.
(2) B1Y1B2Y2ཻD,ôXD·,·Ψһì.
֤߶A1Y1A2Y2Ҫôغ,Ҫôཻ.
ƽаƽ·,߶Φ1l1,2l2,ô·l1,l2Ľܻڦ1,2Ķ˵֮.,Ҫ·뾭߶Φ1,2,ô·ò߶εĶ˵λ.ʱ,·ͨĶ˵֪,ô·ɷֽɸ,еÿⶼǼ·,ǰķ,Щⶼúܼ򵥵㷨.ɴ˿.
ƽ·⣺ƽһཻfABC(BC),fDEF(EF),ҪAD,ξBC,EF·.
Ȼ,·(A,D)пܾ߶BC,EFĶ˵.(A,D)߶εĶ˵㣨ʧһ,ö˵ΪB,(A,D)ɷֽΪ(A,B)린(B,D).ǰ,(A,B)린(B,D)ļ൱,˿ɵĽۣ˵·ļ൱򵥵.ٶ·߶ζ˵.

ͼ65˵
ƽаƽ·,ɵã
5. ͼ6ʾ,fABC(BC)L1,fDEF(EF)L2,WΪBCEFתL2ϵĹ켣,AE,F·BCĽֱΪG,H,G,HWϵĶӦΪG,H,l1l2ΪֱͨE,GF,HֱߣAD·Ϊ(A,D),ô
(1) l1l2ཻڵO,O߶FH֮⣻
(2) ߶ODEFཻ˵E,F,(A,D)EFཻҲڶ˵㣻,(A,D)˵EFཻ.
֤l1l1ΪEΪԴ㡢ֱʸEGGEͬߣl2l2ΪFΪԴ㡢ֱʸFHHFͬߣ覰(A,D)BCĽΪQ,QWϵĶӦΪQ,
(1) ȡY1l1Y2l1,ݶ4,߶GY1HY2ཻ,Ӷɵl1l2Ҫôƽ,ҪôཻFH֮ĵ.l1l2ƽ,ȻWEFƽ,BCEFƽ,ì,Ӷ֤˶ĵ1.
(2) D߶EFl1,l2ɵڣl1,l2ϵĵ㣩,(A,D)BC,EFĽ϶߶GH,EFڣ,Q߶GH֮,Ȼ߶QDHFGEཻ,붨4ì.
֤ͬ,DEF,l1l2ɵ֮⣨l1l2ϵĵ㣩,(A,D)EFĽΪEF.
ע,ͼ6,(A,D)ĳΪAQ+QDDQ,DQӳ߲һO.
ΪɽX,1,...,m1m1+1,...,m1+m2,YֱչƽL1L2,͹·ΪXL1YL2,ξ߶Φm1,m1+1·.X(Y)m1(m1+1)˵,·ֿΪƽf(m1)f(m1+1)·.
4Ͷ5˵,͹·ɹΪƽμ·,ֻҪҵtlڵıߣף5,ҳYڵĽ,ҵ·ı,Ҳҵ˦m1m1+1,ڳʱtl.μ3ͼ4,ݦm1m1+1tl㷨ɼ£ݲߵչ,X,A,Bֱ,A,B,Yֱ,ֱ߷̹ɵķ鼴A,B.
߿ʵ,m1ɵtڵıߣm1+1lڵıߣɷΪ3Ӷ,,m1ϵӶΣΪseg1(t),seg2(t)m1+1ϵӶΣΪseg1(l),seg2(l).ݶ2,seg1(t)SΪԴseg1(l)seg2(l)ϵͶӰ3Ӷ,seg1(t)ڦm1+1ϵͶӰֻ6ӶΣͬ,seg2(t)ڦm1+1ϵͶӰҲֻ6Ӷ.,m1SΪԴڦm1+1ϵͶӰֻ12Ӷ,Ӷɵ.
1. m1ڦm1+1ϵӰֻ12Ӷ.
3 
Ӧõף5ݵ㷨,㷨ɵĲΪn1+n2,ڵ1n1֮,ĿΪO(n1)ڵn1+1n1+n2֮,ĿΪO(12n2),ɴ˿ɵ½.
6. ͹P1,P2,ǵıΪS1,S2,Ϊn1,n2XS1,ҪX,S1,S2YS2·.Ľʱ临ӶΪO(n21+12n22).
˽Ӧõ̶Ŀ͹,ԵõĽۣ
7. k͹P1,...,Pk,ǵıΪS1,...,Sk,Ϊn1,...,nkXS1,ҪX,ξS1,...,SkYSk·.Ľʱ临ӶΪO(x12i-1n2i).
л ĵҪойѧԺѧо,ڴ˸лλ쵼ͬ־֧.
оõȻѧ𡢹863߿ƼĿйѧԺԺر.ʩ,1969,ʿ,ʦ,ҪоΪ˹,֪ʶ,,,CAI.
ͨѶϵ:ʩ,ൺ266071,ൺн·11źżż
ߵλżżġൺ266071ѧѧ뼼ϵ100871
ο
1Lozano-Perez T, Wesley M A. An algorithm for planning collision-free paths among polyhedral obstacles. Journal of ACM, 1979,22:560570
2Canny J, Reif J. New lower bound techniques for robot motion planning problems. In: Proceedings of the 28th Annual IEEE Symposium. New York: Foundations of Computer Science, IEEE, 1987. 4960
3John H R, James A S. A single-exponential bound for finding shortest paths in three dimensions. Journal of ACM, 1994,41(5):10131019
4Sharir M, Schorr A. On shortest paths in polyhedral spaces. SIAM Journal of Computing, 1986,15:193215
5Chen Jin-dong, Han Yi-jie. Shortest paths on a polyhedron. In: Proceedings of the 6th Annual Symposium on Computing Geometry. 1990. 360369
6Baltsan A, Sharir M. On the shortest paths between two convex polyhedra. Journal of ACM, 1988,35(2):267287
7Mount D M. The number of shortest paths on the surface of a polyhedron, SIAM Journal of Computing, 1990,19(4):593611
8Garey M R, Johnsosn D S. Triangulating a simple polygon. Information Processing Letters, 1978,7(4):175179
1997-11-11յԭ 
1998-07-20յ޸ĸ
