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
Reports

An Elementary Algorithm for Reporting Intersections of Red/Blue Curve Segments

Jean-Daniel Boissonnat 1 Antoine Vigneron 1
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Let E_r and E_b be two sets of x-monotone and non-intersecting curve segments, E=E_r \cup E_b and |E|=n. We give a new sweep-line algorithm that reports the $k$ intersecting pairs of segments of E. Our algorithm uses only three simple predicates that allow to decide if two segments intersect, if a point is left or right to another point, and if a point is above, below or on a segment. These three predicates seem to be the simplest predicates that lead to subquadratic algorithms. Our algorithm is almost optimal in this restricted model of computation. Its time complexity is $O((n+k)\logn) and it requires O(n) space. The same algoritm has been described in our previous report [5]. That report presented also an algoritm for the general case but its analysis was not not correct.
Document type :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00072646
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 10:29:31 AM
Last modification on : Friday, February 4, 2022 - 3:23:57 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:00:11 PM

Identifiers

  • HAL Id : inria-00072646, version 1

Collections

Citation

Jean-Daniel Boissonnat, Antoine Vigneron. An Elementary Algorithm for Reporting Intersections of Red/Blue Curve Segments. [Research Report] RR-3999, INRIA. 2000, pp.13. ⟨inria-00072646⟩

Share

Metrics

Record views

58

Files downloads

200