An optimal visibility graph algorithm for triangulated simple polygons

LetP be a triangulated simple polygon withn sides. The visibility graph ofP has an edge between every pair of polygon vertices that can be connected by an open segment in the interior ofP. We describe an algorithm that finds the visibility graph ofP inO(m) time, wherem is the number of edges in the visibility graph. Becausem can be as small asO(n), the algorithm improves on the more general visibility algorithms of Asanoet al. AAGHI] and Welzl W], which take (n ²) time, and on Suri'sO(m logn) visibility graph algorithm for simple polygons S].This work was supported in part by a U.S. Army Research Office fellowship under agreement DAAG29-83-G-0020.