請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38292
標題: The Smallest Pair of Non-crossing Paths in a Rectilinear Polygon
作者: C.D.Yang
D.T.Lee
C.K.Wong
出版社: IEEE Computer Society Washington, DC, USA
摘要: Smallest rectilinear paths are rectilinear paths with a minimum number of bends and with a minimum length simultaneously. In this paper given two pairs of terminals within a rectilinear polygon, we derive an algorithm to find a pair of non-crossing rectilinear paths within the polygon such that the total number of bends and the total length are both minimized. Although a smallest rectilinear path between two terminals in a rectilinear polygon always exists, we show that such a smallest pair may not exist for some problem instances. In that case the algorithm presented will either find among all non-crossing paths with a minimum total number of bends, a pair whose total length is the shortest, or find among all non-crossing paths with a minimum total length, a pair whose total number of bends is minimized. We provide a simple linear time and space algorithm based on the fact that there are only a limited number of configurations of such a solution pair.
URI: http://hdl.handle.net/11455/38292
ISSN: 0018-9340
顯示於類別:資訊科學與工程學系所

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


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