inria-00074791, version 1
Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers
Olivier Devillers
1Andreas Fabri
1
N° RR-1882 (1993)
Résumé : We present output-sensitive scalable parallel algorithms for bichromatic line segment intersection problems for the coarse grained multicomputer model. Under the assumption that n 3 p2, where n is the number of line segments and p the number of processors, we obtain an intersection counting algorithm with a time complexity of 0(F(n log n log p;p) + T,(n log p, p)), where T,(m, p) is the time used to sort m items on a p processor machine. An additional 0(F(k;p) ) time is spent on the reporting of the k intersections. As the sequential complexity is 0(n log n) and 0(k) for counting and reporting, respectively, we obtain a speedup of F(p;log p) .As a byproduct we present algorithms for the trapezoidal de composition and 1-dimensional range query reporting with the same speedup.
- 1 : PRISME (INRIA Sophia Antipolis)
- INRIA
- Domaine : Informatique/Autre
- Référence interne : RR-1882
- inria-00074791, version 1
- http://hal.inria.fr/inria-00074791
- oai:hal.inria.fr:inria-00074791
- Contributeur : Rapport De Recherche Inria
- Soumis le : Mercredi 24 Mai 2006, 16:22:11
- Dernière modification le : Vendredi 2 Mars 2007, 11:48:37






Documents associés

Exporter