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 k~(1/2) log (n~2/k)) expected time. In the bichromatic case (where segments are colored red or blue with no red/red or blue/blue intersections), we find a better algorithm that runs in O(n + k) log_(2+k)n) worst-case time, by modifying a known segment-tree method. Two questions of Boissonnat and Snoeyink are thus answered to within logarithmic factors.