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

Tetsuo ASANO

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

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

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.