HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Robust Plane Sweep for Intersecting Segments

Jean-Daniel Boissonnat 1 Franco Preparata
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In this paper, we reexamine in the framework of robust computation the Bentley-Ottmann algorithm for reporting intersecting pairs of segments in the plane. This algorithm has been reported as being very sensitive to numerical errors. Indeed, a simple analysis reveals that it involves predicates of degree 5, presumably never evaluated exactly in most implementation. Within the exact-computation paradigm we introduce two models of computation aimed at replacing the conventional model of real-number arithmetic. The first model (predicate arithmetic) assumes the exact evaluation of the signs of algebraic expressions of some degree, and the second model (exact arithmetic) assumes the exact computation of the value of such (bounded-degree) expressions. We identify the characteristic geometric property enabling the correct report of all intersections by plane sweeps. Verification of this property involves only predicates of (optimal) degree 2, but its straighforward implementation appears highly inefficient. We then present algorithmic variants that have low degree under these models and achieve the same performance as the original Bentley-Ottmann algorithm. The technique is applicable to a more general case of curved segments.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 12:45:10 PM
Last modification on : Friday, February 4, 2022 - 3:17:36 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:46:02 PM


  • HAL Id : inria-00073419, version 1



Jean-Daniel Boissonnat, Franco Preparata. Robust Plane Sweep for Intersecting Segments. RR-3270, INRIA. 1997. ⟨inria-00073419⟩



Record views


Files downloads