We present a space-efficient algorithm for reporting all k intersections induced by a set of n line segments in the plane. Our algorithm is an in-place variant of Balaban's algorithm and, in the worst case, runs in O(n log 2 n + k) time using O(1) extra words of memory in addition to the space used for the input to the algorithm.
Later Vahrenhold REF improved the time complexity of this problem to O(n log 2 n + k).
Line-segment intersection made in-place
Comput. Geom.
Comput. Geom.
Mathematics Computer Science