Technical Reports

The ICICS/CS Reading Room

UBC CS TR-93-32 Summary

Counting and Reporting Red/Blue Segment Intersections, October 1993 Larry Palazzi, 20 pages

We simplify the red/blue segment intersection algorithm of Chazelle et al: 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 proportional to their number. Our algorithm uses a plane sweep to presort the segments; then it operates on a list of slabs that efficiently stores a single level of a segment tree. With no dynamic memory allocation, low pointer overhead, and mostly sequential memory reference, our algorithm performs well even with inadequate physical memory.

If you have any questions or comments regarding this page please send mail to