An Efficient Algorithm for Finding the Visibility Polygon for a Polygonal Region with Holes

Tetsuo ASANO  

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


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




Summary: 
We are given a polygonal region P with holes and one point q is specified in the region. The problem is how fast we can find the portion of the boundary of P that is visible from q. For this problem an efficient algorithm is presented which runs in time O(n log h) in the worst case and in time O(n+h log h) if every hole is a convex polygon, where n is the total number of vertices of P and h is the number of holes.