文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > k-Link Rectilinear Shortest Paths Among Rectilinear Obstacles in the Plane
侵权投诉

k-Link Rectilinear Shortest Paths Among Rectilinear Obstacles in the Plane

We present an algorithm for computing k-link rectilinear shortest paths among rectilinear obstacles in the plane. We extend the “continuous Dijkstra ” paradigm to store the link distance information associated with each propagating “wavefront”. Our alg

References

e

 

 

cruos- hv-source

 

 

    

v-source

 

e

cruo 

 s-hv-source

 p

Figure5:AnotherTypeIIIevent.

tocomputingrectilinearpathsamonggeneral(non-rectilinear)polygonalobstacles.Also,itshouldbepos-sibletoreduceonefactoroflognfromthetimecom-plexitybyapplyingamorecarefulaccountingscheme,whichhasledtocontinuousDijkstraalgorithmswithcomplexityO(nlogn)forL1shortestpathsamongob-stacles[5,8].Further,byapplyingthealgorithmtomultiple xedorientationsofpathlinks,andpossiblytoweightedsubdivisions,onecouldaddressmoregen-eralversionsofthek-linkshortestpathproblem,ashasbeenrecentlystudiedin[3].

4

[1]E.M.Arkin,J.S.B.Mitchell,andC.D.Piatko.Bicri-teriashortestpathproblemsintheplane.InProc.3rd

Canad.Conf.Comput.Geom.,pages153–156,1991.[2]D.Z.Chen,O.Daescu,andK.S.Klenk.Ongeomet-ricpathqueryproblems.Internat.J.Comput.Geom.Appl.,11(6):617–645,2001.[3]O.Daescu,J.S.Mitchell,S.Ntafos,J.D.Palmer,and

C.K.Yap.k-linkshortestpathsinweightedsubdivi-sions.InProc.9thWorkshopAlgorithmsDataStruct.,pagetoappear,2005.[4]M.deBerg,M.vanKreveld,B.J.Nilsson,andM.H.

Overmars.Shortestpathqueriesinrectilinearworlds.Internat.J.Comput.Geom.Appl.,2(3):287–309,1992.[5]J.HershbergerandS.Suri.Anoptimalalgorithmfor

Euclideanshortestpathsintheplane.SIAMJ.Com-put.,28:2215–2256,1999.[6]D.T.Lee,C.D.Yang,andC.K.Wong.Rectilin-earpathsamongrectilinearobstacles.DiscreteAppl.Math.,70:185–215,1996.[7]J.S.B.Mitchell.Planningshortestpaths.Ph.D.thesis,

StanfordUniv.,Stanford,CA,1986.[8]J.S.B.Mitchell.Anoptimalalgorithmforshortestrec-tilinearpathsamongobstacles.InAbstracts1stCanad.Conf.Comput.Geom.,page22,1989.

[9]J.S.B.Mitchell.L1shortestpathsamongpolygonal

obstaclesintheplane.Algorithmica,8:55–88,1992.[10]J.S.B.Mitchell.Geometricshortestpathsandnetwork

optimization.InJ.-R.SackandJ.Urrutia,editors,HandbookofComputationalGeometry,pages633–701.ElsevierSciencePublishersB.V.North-Holland,Ams-terdam,2000.[11]J.S.B.Mitchell.Shortestpathsandnetworks.In

J.E.GoodmanandJ.O’Rourke,editors,HandbookofDiscreteandComputationalGeometry(2ndEdition),chapter27,pages607–641.Chapman&Hall/CRC,BocaRaton,FL,2004.[12]J.S.B.Mitchell,C.Piatko,andE.M.Arkin.Com-putingashortestk-linkpathinapolygon.InProc.33rdAnnu.IEEESympos.Found.Comput.Sci.,pages573–582,1992.[13]C.D.Piatko.GeometricBicriteriaOptimalPathProb-lems.Ph.D.thesis,CornellUniversity,1993.

[14]C.D.Yang,D.T.Lee,andC.K.Wong.Onbendsand

lengthsofrectilinearpaths:agraphtheoreticapproach.Internat.J.Comput.Geom.Appl.,2(1):61–74,1992.[15]C.D.Yang,D.T.Lee,andC.K.Wong.Rectilinear

pathsproblemsamongrectilinearobstaclesrevisited.SIAMJ.Comput.,24:457–472,1995.

上一页第4页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email