Optimal algorithm for computing visibility in the plane

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 Θ(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.