請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38373
標題: Rectilinear Shortest Paths with Rectangular Barriers
作者: Rezende, P.J.de
D.T.Lee
Y.F.Wu
出版社: ACM New York, NY, USA
摘要: We address ourselves to an instance of the Shortest Path problem with obstacles where a shortest path in the Manhattan (or L1) distance is sought between two points (source and destination) and the obstacles are n disjoint rectangles with sides parallel to the coordinate axes. A plane sweep technique is applied rather than the graph theoretic approach frequently used in the literature. We show that there has to be a path of minimum length between the two given points which is monotone in at least one of x or y directions. Then we present an algorithm of time complexity &Ogr;(n log n) for constructing that path and show that our algorithm is optimal. Lastly, we address the query form of this problem in which given a source point and n obstacles, after &Ogr;(n log n) time for preprocessing, a shortest path from the source point to a query point avoiding all the obstacles can be reported in &Ogr;(t + log n) time, where t is the number of turns on the path.
URI: http://hdl.handle.net/11455/38373
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。