An $O(E\log E + I)$ Expected Time Algorithm for the Planar Segment Intersection Problem
Eugene Wimberly Myers · SIAM Journal on Computing · 1985
It is an open question in computational geometry as to whether there exists an $O(E\log E + I)$ algorithm to determine the I intersections of a collection of E line segments in the plane. An approach utilizing a work list bubble sort and a distribution-based search is presented. The resulting algorithm has $O(E\log E + I)$ expected time complexity. In the worst case the algorithm has the same complexity as the algorithm of Bentley and Ottmann [IEEE Trans. Comput., 28 (1979), pp. 643–647]: $O(E\log E + I\log E)$. The algorithm requires only $O(E)$ space and in contrast to prior work, no restrictions are placed upon the nature of the intersections.