An Elementary Algorithm for Reporting Intersections of Red/Blue Curve Segments - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2000

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

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-3999.pdf (200.12 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00072646 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00072646 , version 1

Citer

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⟩
66 Consultations
225 Téléchargements

Partager

Gmail Facebook X LinkedIn More