**Abstract. ** We present a new line sweep algorithm, HEAPSWEEP, for reporting bichromatic (``purple'') intersections between a red and a blue family of line segments. If the union of the segments in each family is connected as a point set, HEAPSWEEP reports all

*k* purple intersections in time

*O((n+k) α(n)* log

^{ 3 } * n)* , where

*n* is the total number of input segments and

*α(n)* is the nearly constant inverse Ackermann function. To achieve these bounds, the algorithm maintains only partial information about the vertical ordering between curves of the same color, using a new data structure called a

*kinetic queue* . In order to analyze the running time of HEAPSWEEP, we also show that a simple polygon containing a set of

*n* line segments can be partitioned into monotone regions by a set of vertical threads cutting these segments

*O(n* log

*n)* times.