文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 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

h-source

v-source

v-sources

Figure3:TypeIIevent.

  

 

~

   

h-source

 

p  

v-source

v-source

Figure2:TypeIevent.

Complexityofthealgorithm.Sincewearepropagat-inguptokdi erentwavefronts(correspondingtouptokdi erentlinkdistancestothepointsonwavefronts),thecomplexityofthealgorithmin[9]goesupbyafactorofkandbecomesO(knlog2n).

Theproofofcorrectnessisbasedonaninductionar-gument,establishingthateachpointtreached(sweptover)bytheithevent(withassociatedL1distancedi)havebeenreachedbyadraggedsegmentcorrespond-ingtoeachofthelinkdistancesj=dL(s,t),...,l(t),wheredL(s,t)istherectilinearlinkdistancefromstotandl(t)isthe(maximum)rectilinearlinklengthofashortestL1pathfromstot.

3

p 

v-source

Figure4:TypeIIIevent.

3

Conclusion

Weexpectthatourresultscanbeextendedandim-proved.First,weexpectthatourmethodapplies

h-source

  ~

h-source

~

 

~

h-sources

Events.Thepropagationofthewavefrontinvolvesdo-ingdi erentthingsdependingonwhetherthenextevent

isofTypeI,II,orIIIandonwhetherornottheeventpointphasalreadybeenpermanentlylabeled.ThecasesareillustratedinFigures2,3,4and5foraseg-mentdraggednortheast.Processingtheeventsforthesegmentspropagatinginotherdirectionsissimilar.Thedetailsoftheeventsprocessingaremostlythesameasin[9].Itisimportant,though,tomodifytheclippingofwavefrontsinorderthattheonlywavefrontsthatarepermittedtocontinue(andnotbeclippedappro-priately)arethosecorrespondingtoPareto-optimalso-lutionpaths.

~

 p v-source

~

~

h-source

draggedsegmentsrootedatsareinsertedalongwiththeirdistancelabelsintotheeventqueue:NE,NW,SWandSEsegmentswiththetracksbeinghorizontalandverticalraysfroms.

 

~

上一页第3页

你可能喜欢

热门文档

相关文档

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