Robust plane sweep for intersecting segments

In this paper, we reexamine in the framework of robust computation the Bent ley-Ottmann algorithm for reporting intersecting pairs of segments in the p lane. This algorithm has been reported as being very sensitive to numerical errors. Indeed, a simple analysis reveals that it involves predicates of d egree 5, presumably never evaluated exactly in most implementations. Within the exact-computation paradigm we introduce two models of computation aime d at replacing the conventional model of real-number arithmetic. The first model (predicate arithmetic) assumes the exact evaluation of the signs of a lgebraic expressions of some degree, and the second model (exact arithmetic ) assumes the exact computation of the value of such (bounded-degree) expre ssions. We identify the characteristic geometric property enabling the corr ect report of all intersections by plane sweeps. Verification of this prope rty involves only predicates of (optimal) degree 2, but its straightforward implementation appears highly inefficient. We then present algorithmic var iants that have low degree under these models and achieve the same performa nce as the original Bentley Ottmann algorithm. The technique is applicable to a more general case of curved segments.