Reporting Curve Segment Intersections Using Restricted Predicates

We investigate how to report all k intersecting pairs among a collection of n x-monotone curve segments in the plane, using only predicates of the following forms: is an endpoint to the left of another? is an endpoint above a segment? do two segments intersect? By studying the intersection problem in an abstract setting that assumes the availability of certain "detection oracles," we obtain a near-optimal randomized algorithm that runs in O(n log n+n expected time. In the bichromatic case (where segments are colored red or blue with no red/red or blue/blue intersections), we nd a better algorithm that runs in O((n + k) log 2+k=n n) worst-case time, by modifying a known segment-tree method. Two questions of Boissonnat and Snoeyink are thus answered to within logarithmic factors