Red-Blue Intersection Reporting for Objects of Non-Constant Size
Panayiotis Bozanis · The Computer Journal · 1996
Let Q 1 be a set of'red' geometric objects and Q 2 a set of 'blue' ones. The objects in Q 1 and Q 2 are of arbitrarily large description size but each one is the union of simpler constant size components. We consider the problem of reporting all intersections between objects of Q 1 and objects of Q 2 in a time that depends on the size of the output. This is equivalent to painting the constant size objects in Q 1 and Q 2 and reporting colour intersections between Q 1 and Q 2 . We present a technique that yields simple output-sensitive algorithms for many kinds of geometric objects. We also show that, using the same technique, it is possible to report all intersecting pairs in a set of objects in an output-sensitive manner.