1991/06/01 by János Pach, Micha Sharir · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Digital Image Processing Techniques #Combinatorics #Line segment #Line (geometry) #Upper and lower bounds #Mathematics #Point (geometry) #Queue #Omega #Visibility #Binary logarithm #Algorithm #Geometry #Computer science #Physics #Mathematical analysis #Optics
paper · doi:10.1137/0220029
openalex publication_date 1991/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
Let S = \ e1 , ⋯ ,en \ 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 (ei, ej are vertically visible if there exists a vertical line segment connecting a point on ei to a point on ei and not meeting any other segment). It is shown that there are at most O(nlog 2 n) such pairs, and only O(nlog 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(n4 / 3 (log n)2 / 3 ), and can be Ω (n4 / 3 ) in the worst case.