Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers

Olivier Devillers 1 Andreas Fabri 1
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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.
Type de document :
Rapport
[Research Report] RR-1882, INRIA. 1993
Liste complète des métadonnées

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

Fichiers

Identifiants

  • HAL Id : inria-00074791, version 1

Collections

Citation

Olivier Devillers, Andreas Fabri. Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers. [Research Report] RR-1882, INRIA. 1993. 〈inria-00074791〉

Partager

Métriques

Consultations de la notice

277

Téléchargements de fichiers

65