Elementary Algorithms for Reporting Intersections of Curve Segments

Jean-Daniel Boissonnat 1 Antoine Vigneron
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We propose several algorithms to report the k intersecting pairs among a set of n curve segments. Apart from the intersection predicate, our algorithms only use two simple predicates : the predicate that compares the coordinates of two points and the predicate that says if a point is below, on, or above a segment. In particular, the predicates we use do not allow to count the number of intersection points nor to sort them, and the time complexity of our algorithms depends on the number of intersectin- g pairs, not on the number of intersection points (differently from the other non trivial algorithms). We present an algorithm for the red-blue variant of the problem where we have a set of blue segments and a set of red segments so that no two segments of the same set intersect. The time complexity is O((n+k)\log n). This algorithm is then used to solve the general case in O(n\sqrtk\log n) time. In the case of pseudo-segments (i.e. segments that intersect in at most one point) we propose a better algorithm whose time complexity is O((k+n)\log n+ n\sqrt k). All our time complexity results are a log factor from optimal.
Type de document :
Rapport
RR-3825, INRIA. 1999
Liste complète des métadonnées

https://hal.inria.fr/inria-00072833
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 11:03:59
Dernière modification le : samedi 27 janvier 2018 - 01:31:05
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:24:24

Fichiers

Identifiants

  • HAL Id : inria-00072833, version 1

Collections

Citation

Jean-Daniel Boissonnat, Antoine Vigneron. Elementary Algorithms for Reporting Intersections of Curve Segments. RR-3825, INRIA. 1999. 〈inria-00072833〉

Partager

Métriques

Consultations de la notice

155

Téléchargements de fichiers

124