An optimal algorithm for finding segments intersections
Ivan J. Balaban · 1995
This paper deals with a new deterministic algorithm for finding intersecting pairs from a given set of N segments in the plane.The algorithm is asymptotically optimal and has time and space complexity O(AJ log N+ K) and 0( IV ) respectively, where K is the number of intersecting pairs.The algorithm may be used for finding intersections not only line segments but also curve segments.