Sweeping lines and line segments with a heap
Julien Basch, Leonidas Guibas, G. D. Ramkumar · 1997
Given n line segments in the plane, the Bentley-Ottmann sweep maintains the exact ordering of the intersections of the segments with a vertical line, as this line sweeps the plane from left to right. To accomplish this, every intersection between two segments must be processed, and the running time of the sweep can be \\Omega\\Gamma n 2 ). In this paper, it is shown how a heap on the intersections can be maintained during the sweep. This new type of sweep processes O(n log 2 n) intersections when sweeping over lines and O(n p n log n) intersections when sweeping over line segments. A lower bound of \\Omega\\Gamma n log n) is also established. 1 Introduction One of the common introductory problems in geometric algorithms is that of finding all pairwise intersections in a family of line segments in the plane. The first nontrivial solution to this problem was given by Bentley and Ottmann [BO79], who introduced in 1979 the now familiar line sweep paradigm. A vertical line is moved (`swe...