Finding the visibility graph of a simple polygon in time proportional to its size
John E. Hershberger · 1987
Let P be a given simple polygon with n sides. The visibility graph of P has an edge between every pair of polygon vertices that can be connected by an open segment in the interior of P. We describe an algorithm that finds the visibility graph of P in O(m + n log log n) time, where m is the number of edges in the visibility graph. Because m can be as small as O(n), the algorithm improves on the more general visibility algorithms of Asano et al. [AAGHI] and Welzl [W], which take T(n2) time.