On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm
János Pach, Micha Sharir · SIAM Journal on Computing · 1991
Let $S = \{ e_1 , \cdots ,e_n \} $ be a collection of n (intersecting) line segments in the plane. Suppose that all segments have their right endpoints lying on the same vertical line, and that one wishes to bound the number of pairs of nonintersecting vertically visible segments that will intersect when extended to the right ($e_i$, $e_j$ are vertically visible if there exists a vertical line segment connecting a point on ei to a point on $e_i$ and not meeting any other segment). It is shown that there are at most $O(n\log ^2 n)$ such pairs, and only $O(n\log n)$ in the case of full rays, where the latter bound can be attained in the worst case. These results are applied to obtain similar upper and lower bounds on the maximum size of the queue in the original implementation of the Bentley–Ottmann algorithm for reporting all intersections between the segments in S, i.e., the implementation where future events are not deleted from the queue. It is also shown that, without the extra conditions on the segments in S and on the pairs of segments to be counted, the number of nonintersecting vertically visible pairs of segments is $O(n^{4 / 3} (\log n)^{2 / 3} )$, and can be $\Omega (n^{4 / 3} )$ in the worst case.