A fast algorithm for computing sparse visibility graphs

An O(|E|log2 n) algorithm is presented to construct the visibility graph for a collection of n nonintersecting line segments, where |E| is the number of edges in the visibility graph. This algorithm is much faster than the O(n 2)-time and O(n 2)-space algorithms by Asano et al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses only O(n) working storage. © 1990 Springer-Verlag New York Inc.