An optimal visibility graph algorithm for triangulated simple polygons (Q1114399)

Let P be a triangulated 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) 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 \textit{T. Asano}, \textit{L. Guibus}, \textit{H. Imai} and the author [ibid. 1, 49-63 (1986; Zbl 0611.68062)] and \textit{E. Welzl} [Inf. Process. Lett. 20, 167-171 (1985; Zbl 0573.68036)], which take \(\theta (n^ 2)\) time.