A tight lower bound on the size of visibility graphs (Q1098639)

The visibility graph of a finite set of line segments in the plane connects two endpoints u and v if and only if the straight line connection between u and v does not cross any line segment of the set. The article proves that the visibility graph of n nonintersecting line segments has at least 5n-4 edges. This lower bound is tight. The result is of some interest in connection with the following problem: Is there an algorithm for constructing the visibility graph which takes less than \(\Omega\) (n 2) time if the number of edges of this graph is subquadratic?