An Efficient Algorithm for Finding the Region Reachable within k Bends

Tetsuo ASANO  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E68   No.12   pp.831-835
Publication Date: 1985/12/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Programming
Keyword: 


Full Text: PDF(399.3KB)>>
Buy this Article




Summary: 
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.