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≥p^2, 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 O( (n log n log p)/p + Ts(n log p,p) ), where Ts(m, p) is the time used to sort m items on a p processor machine. The first term captures the time spent in sequential computation performed locally by each processor. The second term captures the interprocessor communication time. An additional O(k/p) time in sequential computation is spent on the reporting of the k intersections. As the sequential time complexity is O(n log n) for counting and an additional time O(k) for reporting, we obtain a speedup of p/log p in the sequential part of the algorithm. The speedup in the communication part obviously depends on the underlying architecture. For example for a hypercube it ranges between p/log^2p and p/log p depending on the ratio of n and p. As the reporting does not involve more interprocessor communication than the counting, the algorithm achieves a full speedup of p for k≥ O(max(n log n log p, n log^3 p)) even on a hypercube.
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 1996, 6 (4), pp.487-506. 〈10.1142/S0218195996000307〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00795079
Contributeur : Olivier Devillers <>
Soumis le : mercredi 27 février 2013 - 11:30:14
Dernière modification le : samedi 27 janvier 2018 - 01:31:39

Lien texte intégral

Identifiants

Collections

Citation

Olivier Devillers, Andreas Fabri. Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers. International Journal of Computational Geometry and Applications, World Scientific Publishing, 1996, 6 (4), pp.487-506. 〈10.1142/S0218195996000307〉. 〈hal-00795079〉

Partager

Métriques

Consultations de la notice

161