An Optimal Algorithm for Computing Visibility in the Plane
Paul J. Heffernan, Joseph S. B. Mitchell · SIAM Journal on Computing · 1995
The authors give an algorithm to compute the visibility polygon from a point among a set of h pairwise-disjoint polygonal obstacles with a total of n vertices. The algorithm uses $O(n)$ space and runs in optimal time $\Theta (n + h \log h)$, improving the previous upper bound of $O(n \log n)$. A direct consequence of the algorithm is an $O(n + h \log h)$ time algorithm for computing the convex hull of h disjoint simple polygons.