COUNTING AND REPORTING RED BLUE SEGMENT INTERSECTIONS/

We simplify the red/blue segment intersection algorithm of Chazelle et al. (Technical Report UIUC DCS-R-90-1578, Department of Computer Scie nce, University of Illinois at Urbana, 1990). Given sets of n disjoint red and n disjoint blue segments, we count red/blue intersections in O(n log n) time using O(n) space or report them in additional time pro portional to their number. Our algorithm uses a plane sweep to presort the segments; then it operates on a list of slabs that efficiently st ores a single level of a segment tree. With no dynamic memory allocati on, low pointer overhead, and mostly sequential memory reference, our algorithm performs well even with inadequate physical memory. (c) 1994 Academic Press, Inc.