Computing the Visibility Polygon of an Island in a Polygonal Domain

摘要

Given a set P of h pairwise-disjoint polygonal obstacles with a total of n vertices in the plane, we study the problem of computing the (weak) visibility polygon from a polygonal obstacle P* (an island) in P. The problem was previously solved in O(n(4)) time, which has been proved worst-case optimal. However, since h may be much smaller than n, it is desirable to have an algorithm whose running time is also a function of h. In this paper, we present such an algorithm of O(n(2)h(2)) time, and our algorithm improves the previous result when h = o(n). In addition, when all obstacles in P (including P*) are convex, our algorithm runs in O(n + h(4)) time.