Computing the Visibility Polygon of an Island in a Polygonal Domain.

Given a set $${\mathcal {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 $${\mathcal {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^2h^2)$$ time, and our algorithm improves the previous result when $$h=o(n)$$ . In addition, when all obstacles in $${\mathcal {P}}$$ (including $$P^*$$ ) are convex, our algorithm runs in $$O(n+h^4)$$ time. [ABSTRACT FROM AUTHOR]