For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Efficient Algorithm for Finding the Region Reachable within k Bends
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1985/12/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Full Text: PDF(399.3KB)>>
Among the most fundamental problems in the layout design of an integrated circuit is the following problem: Given a region bounded by n orthogonal line segments and a point q in its interior, find the region that is reachable from q along rectilinear paths with at most k bends which avoid obstructions, where k is some given constant. In this paper we present an efficient algorithm which determines such a region in O(kn) time for a rectilinear simple polygon without any hole in it.