An Efficient Algorithm for Computing the k-Reachability Region from a Point

Tetsuo ASANO  

IEICE TRANSACTIONS (1976-1990)   Vol.E68   No.9   pp.560-562
Publication Date: 1985/09/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: LETTER
Category: Data Processing

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

The following problem is considered: Given a rectilinear simple polygon P and a point q in its exterior, find the region that is reachable from q along orthogonal paths with at most k bends. For this problem we preset an efficient algorithm which runs in O(kn) time, where n is the number of vertices.