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

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

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.
Keywords :
Document type :
Reports
Domain :

Cited literature [1 references]

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

### 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⟩

Record views