Line-Segment Intersection Made In-Place

摘要

We present a space-efficient algorithm for reporting all k intersections induced by a set of n line segments in the place. Our algorithm is an in-place variant of Balaban's algorithm and runs in O(n log_2~2 n + k) time using O(1) extra words of memory over and above the space used for the input to the algorithm.