Please use this identifier to cite or link to this item: 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
Project: IEEE Trans. Comput., Volume�46, Issue�8, Page(s) �930-941.
摘要: 
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
DOI: 10.1109/12.609280
Appears in Collections:資訊科學與工程學系所

Show full item record
 

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.