An Efficient Algorithm for Finding the Region Reachable within k Bends

Tetsuo ASANO

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

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

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.